Depth First Search

This technique uses recursion or iterative approach using stack to keep track of all the previous (parent) nodes while traversing trees in a depth-first search manner.

How to Identify

• Data Structure Involves: Tree, Graph
• Question Type: Traverse a tree with in-order, preorder, or postorder.

Example

Recursive

Pre-Order

preOrderTraversal.ts

import {TreeNode} from "./TreeNode"
function preOrderTraversal(root: TreeNode | null, result: number[]) {
  // base case
  if(root === null) return
  
  // recursive case
  result.push(root.val) // <== preorder
  preOrderTraversal(root.left, result)
  preOrderTraversal(root.right, result)
}

In-Order

inOrderTraversal.ts

import {TreeNode} from "./TreeNode"
function inOrderTraversal(root: TreeNode | null, result: number[]) {
  // base case
  if(root === null) return
  
  // recursive case
  inOrderTraversal(root.left, result)
  result.push(root.val) // <== inorder
  inOrderTraversal(root.right, result)
}

Post-Order

postOrderTraversal.ts

import {TreeNode} from "./TreeNode"
function postOrderTraversal(root: TreeNode | null, result: number[]) {
  // base case
  if(root === null) return
  
  // recursive case
  postOrderTraversal(root.left, result)
  postOrderTraversal(root.right, result)
  result.push(root.val) // <== postorder
}

TreeNode

TreeNode.ts

export class TreeNode {
  val: number
  left: TreeNode | null
  right: TreeNode | null
    
  constructor(val?: number, left?: TreeNode | null, right?: TreeNode | null) {
    this.val = (val===undefined ? 0 : val)
    this.left = (left===undefined ? null : left)
    this.right = (right===undefined ? null : right)
  }
}

Iterative

Pre-Order

preOrderTraversal.ts

import {TreeNode} from "./TreeNode"
function dfsPreOrder(root: TreeNode | null): number[] {
  if(root === null) return[]
  const stack = [root]
  const order = []
  
  while(stack.length > 0) {
    const currentNode = stack.pop()
    order.push(currentNode.val)
    
    if(currentNode.right) stack.push(currentNode.right)
    if(currentNode.left) stack.push(currentNode.left)
  }
  
  return order
}

In-Order

inOrderTraversal.ts

import {TreeNode} from "./TreeNode"
function dfsInOrder(root: TreeNode | null): number[] {
  if( root === null) return []
  const stack = []
  const order = []
  let current = root
    
  while(current !== null || stack.length > 0) {
    while(current !== null) {
      stack.push(current)
      current = current.left
    }
    current = stack.pop()
    order.push(current)
    current = current.right
  }
  
  return order
}

Post-Order

postOrderTraversal.ts

import {TreeNode} from "./TreeNode"
function dfsPostOrder(root: TreeNode | null): number[] {
  if(root === null) return[]
  const stack1 = [root], stack2 = [], order = []
  
  while(stack1.length > 0) {
    const currentNode = stack1.pop()
    stack2.push(currentNode)
    
    if(currentNode.left) stack1.push(currentNode.left)
    if(currentNode.right) stack1.push(currentNode.right)        
  }
  
  return stack2.reverse()
}

TreeNode

TreeNode.ts

export class TreeNode {
  val: number
  left: TreeNode | null
  right: TreeNode | null
    
  constructor(val?: number, left?: TreeNode | null, right?: TreeNode | null) {
    this.val = (val===undefined ? 0 : val)
    this.left = (left===undefined ? null : left)
    this.right = (right===undefined ? null : right)
  }
}

Related Problems

	Problems	Difficulty
1	Maximum Depth of Binary Tree	Easy
2	Same Tree	Easy
3	Invert Binary Tree	Easy
4	Subtree of Another Tree	Easy
5	Lowest Common Ancestor of BST	Easy
6	Construct Binary Tree from Preorder and Inorder Traversal	Medium
7	Validate Binary Search Tree	Medium
8	Kth Smallest Element in a BST	Medium
9	Binary Tree Maximum Path Sum	Hard