Depth-First Search of a Binary Tree

In this previous blog post we learned what a binary tree is, how it can be represented, and the different types of binary trees, in conclusion, we’ve said that a binary tree, unlike other data structures, can be browsed in two different ways breath-first search and depth-first search.

This post will be focused on depth-first search.

What’s depth-first search Tree traversal

The depth-first search is an algorithm that allows you to traverse an entire Tree. The logic is that you keep moving forward until you reach a leaf (a node that hasn’t left or right child) then backtrack according to the method you are using.

Depth-first search Tree traversal can be written in three ways: Pre Order, In Order, and Post Oder traversal. Each way can be written recursively and iteratively. The way you choose influences the result. Let’s me show you the difference:

Pre Order

The hint is on the name, Pre-order, when you are writing a pre-order traversal, you access the parent node then the left and the right child. If you traverse the tree above with the Pre Order method your result should be:

Let’s write the recursive and iterative implementation with javascript

Recursive

function dfsPreOrderRecursive(node, arr = []){
  if(node){
    arr.push(node.val); 
    if(node.left) dfsPreOrderRecursive(node.left, arr);
    if(node.right) dfsPreOrderRecursive(node.right, arr);
  }
}

Explanation since you know in which order you have to access the nodes, recursive methods are mostly straightforward. Here We have to access the parent node and then its children. so we push the current node’s value into the result array, and then check if it has a left or right child, if so we call the function by giving the child node and the result array.

Iterative

function dfsPreOrderIterative(root){
  const stack = [root]
  const result = []; 
  let current;

  while(stack.length){
    current = stack.pop(); 
    result.push(current.val);

    if(current.right) stack.push(current.right); 
    if(current.left) stack.push(current.left); 
  }

  return result; 

  }

Explanation: the pre-order traversal is the straightforward method, if there isn’t any constraint you should prior the method. Since we don’t need to check if a node has any children, we push the current node’s value to the result and then check if it has child, if so they will be added into the stack. We push the right left before the right because we are using a stack and it follows the FIFO order.

In Order

For the in-order traversal, you have to access the left child before backtracking to the parent and then the right child. You have to keep moving forward while your current node has a left child. if you traverse the tree above with the In-Order method your result should be:

Let’s write the recursive and iterative implementation with javascript.

Recursive

function dfsInOrderRecursive(node, arr = []){ 
  if(node){
    if(node.left) dfsInOrderRecursive(node.left, arr);
    arr.push(node.val); 
    if(node.right) dfsInOrderRecursive(node.right, arr);
  }

  return arr; 

 }

Explanation: since you know in which order you have to access the nodes, recursive methods are mostly straightforward. Here We have to access the left child before backtracking to the parent and then the right child, so we check if the current node has a left child if so, we call the function by giving the child, once it's done we push the node’s value into the result array and finally we check if a right child exists, if so we call the function by giving the right child.

Iterative

function dfsInOrderIterative(root){
  const stack = []; 
  const result = [];
  let current = root; 

  while(stack.length || current){
    while(current){
      stack.push(current); 
      current = current.left; 
    }
    current = stack.pop();
    result.push(current.val); 
    current = current.right;
  }

  return result;
}

Explanation: For the in-order traversal, we have to push the left child, the parent and then the right child. That means we have to keep moving forward since there is left child. For the iterative implementation, the current loop while browse all the left child and then if there’s no left child, the current node’s value will be pushed into the result.

Post Order

For the post-order traversal, you have to access children before backtracking to the parent. You have to keep moving forward while your current node has children. if you traverse the tree above with the post-Order method your result should be:

Let’s write the recursive and iterative implementation with javascript.

Recursive

function dfsPostOrderRecursive(node, arr = []){
  if(node){
    if(node.left) dfsPostOrderRecursive(node.left, arr);
    if(node.right) dfsPostOrderRecursive(node.right, arr);
    arr.push(node.val);
  }

  return arr;
}

Explanation: since you know in which order you have to access the nodes, recursive methods are mostly straightforward. Here We have to access children before the parent, so we check if the current node has a left or right child if so, we call the function by giving the child and then we push the value into the result array.

Iterative

function dfsPostOrderIterative(root){
  const s1 = [root];
  const s2 = [];
  const result = []; 
  let current;

  while(s1.length){
    current = s1.pop();

    if(current.left) s1.push(current.left);
    if(current.right) s1.push(current.right);

    s2.push(current.val);
  }

  return s2.reverse();

}

Complexity analysis

Every approach that we have seen in this post has the same time and space complexity O(n) even the recursive approach because each recursive function use stack under the hood, to track the elements that you are traversing. Your choice will depend on the question you have to solve.