Binary Tree Traversals

Binary tree is a special case of a tree in which there are no more than 2 children for any node. The children are called left and right nodes respectively based on the fact whether they are located on the left or right side of the parent node. Binary trees are extensively used in software engineering because it just takes O(log n) for doing most of the day to day operations – insert, update, delete and search. Traversal algorithms are very important concepts in binary trees because if you want to do any type of operation on a binary tree then as a first step, the tree needs to be traversed to find the nodes on which the desired operation need to be performed. The three widely used binary tree traversal algorithms are

1) Preorder traversal
Processing order of the nodes are – parent, all its left descendants and then the right descendants. In other words, Parent is processed before left sub-tree and right sub-tree are processed.

2) Inorder traversal
Processing order of the nodes are – all left descendants, parent and then the right descendants. In other words, left sub-tree is processed before parent and right sub-tree are processed.

3) Postorder traversal
Processing order of the nodes are – all left descendants, right descendants and then finally the parent descendants. In other words, all the children are processed before the parent is processed.

For the impatient code readers, the entire code base for this project can be accessed from my Github repository – Binary Tree Traversal algorithms.

Recursive Solution
A recursive solution best suits the situation where there is a bigger problem that can be broken down into smaller and similar sub problems and so the same solution can be applied over the sub-problems. It is imperative to have a base case after which the solution should start winding up. Recursion can be best understood when the whole process can be visualized with a stack.

Iterative Solution
An iterative solution best suits the situation where there is a bigger problem that can be broken down into smaller problems and every such smaller problem is iteratively solved one after another. There is no connection between an iteration and its successive iterations. As in the case of recursion, an iteration does not pause or wait until all the sub-iterations are complete. And that’s why we need an additional tool(aka data structure) so that we can adapt an iterative solution for tree-traversals. A stack is needed in an iterative solution so that it can be used to temporarily store the nodes in the needed order and then apply the solution or process the node that comes out of the stack.

Preorder traversal
Recursive solution is simple and self-explanatory.

public void preOrderTraversalRecursive(Node node) {
  if (node == null) {
   return;
  }
  
  System.out.println(node);
  if (node.getLeft() != null) {
   preOrderTraversalIterative(node.getLeft());
  }
  if (node.getRight() != null) {
   preOrderTraversalIterative(node.getRight());
  }
 }

Iterative solution for any traversal needs at least a stack. Preorder traversal is the simplest among all the traversal iterative algorithms. To start with, the root node is added to stack. From there on, we navigate deep into the left-most sub-tree. And while doing so, we keep processing the node that we are navigating through and we keep adding the right child of the node (if exists) to the stack. The left child is added too but it is popped out in the next iteration, and that’s how we navigate down the tree. While we pop out the nodes from the stack, we go over the same process – navigate, process and add the right child to stack if it exists.

public void preOrderTraversalIterative(Node node) {
Stack<Node> stack = new Stack<Node>();
  stack.push(node);
  
  while (!stack.isEmpty()) {
   Node poppedNode = stack.pop();
   System.out.println(poppedNode);
   if (poppedNode.getRight() != null) {
    stack.add(poppedNode.getRight());
   }
   
   if (poppedNode.getLeft() != null) {
    stack.add(poppedNode.getLeft());
   }
  }
}

Inorder traversal
The recursive solution is pretty simple. Given a node, keep navigating to the left-most node until a leaf node is reached. Once reached, process the leaf node, its parent and then the right sub-tree (again go through the same above process).

public void inOrderTraversalRecursive(Node node) {
  if (node == null) {
   return;
  }
  
  if (node.getLeft() != null) {
   inOrderTraversalRecursive(node.getLeft());
  }
  System.out.println(node);
  if (node.getRight() != null) {
   inOrderTraversalRecursive(node.getRight());
  }
 }

As expected the iterative solution uses a single stack. The in-order traversal algorithm processes the left sub-tree first from deep down node => which in turn means, navigate to the left-most leaf node. So, as a first step, navigate deep down into the left sub-tree. We keep pushing all the left-nodes to the stack when we navigate, so that when we pop out of the stack for the first time, it’s going to be the left-most leaf node. For every popped node, we check whether there is a right node, if there is, then we add that node and then followed by all left-nodes (if there are) for the right node (that we are working on) to the stack. Once that is done, we pop out a node from the stack and then repeat the same above process until the stack goes empty.

public void inOrderTraversalIterative(Node node) {
  if (node == null) {
   return;
  }

  Stack<Node> stack = new Stack<Node>();
  // Navigate to the left most node of the left sub-tree. During that process, push all the navigating nodes to the stack.
  while (node != null) {
   stack.push(node);
   node = node.getLeft();
  }
  
  while (!stack.isEmpty()) {
   Node currNode = stack.pop();
   System.out.println(currNode);
   
   /* If the current node has a right child, push it to stack and navigate to the left node of that right child if it exists. 
   Remember we need to process the right sub-tree of any parent node. So, add all left nodes of the right child to stack and 
   keep navigating to left till the leaf node */ 
   if (currNode.getRight() != null) {
    Node rightnode = currNode.getRight();
    stack.push(rightnode);
    if (rightnode.getLeft() != null) {
     Node rightsLeftnode = rightnode.getLeft();
     while (rightsLeftnode != null) {
      stack.push(rightsLeftnode);
      rightsLeftnode = rightsLeftnode.getLeft();
     }
    }
   }
  }
 }

Postorder traversal
As always the recursive solution is simple. Given a node, the left descendants are processed first followed by the right descendants and then the node in consideration is processed. It looks pretty simple to do using a recursive approach.

public void postOrderTraversalRecursive(Node node) {
  if (node == null) {
   return;
  }
  
  if (node.getLeft() != null) {
   postOrderTraversalRecursive(node.getLeft());
  }
  
  if (node.getRight() != null) {
   postOrderTraversalRecursive(node.getRight());
  }
  System.out.println(node);
 }

The iterative solution for postorder traversal is the most difficult of all. The below iterative solution uses a single stack. This algorithm may not look same as other solutions provided in internet. This solution worked well for the usecases that I tested and hopefully it works for everyone. The tough part of this solution is: Determining whether we are currently navigating down the tree or up the tree. If we don’t determine that, we might end up looping back and forth in an endless loop. How to identify whether we are going up or down? If we remember the previous node that was processed or added to the stack then based on that, we can tell the relationship of the current node to the previous node. It can be a child node or the parent node!! This determination would help us making a decision whether to move up or down.

On a broad view, there are 2 cases that need to be covered in this algorithm
1) If the current node is the parent of the previously processed node (the previously processed node could either be a left or right child) then it means we are going up the tree. That in turn means we have already processed the child sub-trees of the current node. So, it’s time to process the parent node and go for the next element in the stack.
2) The other situations could be:
a) The current node can be the left or right child of the previously processed node. In this case, we are going down the tree.
b) The current node is the root node.
c) The current node can be the right companion of the previously processed node.

For all the above usecases (a), (b) and (c), we call the special private method “navigateAndProcessNodesInPostOrder” method. navigateAndProcessNodesInPostOrder method takes care of pushing the current node, left child and right child (in that order) to stack if the nodes exist. After pushing the nodes, it navigates to the left child (if it exists) because precedence is given to the left node. If not it tries to navigate to the right child. If there are no child nodes then this method just processes it without the need of adding that to stack because it’s a leaf node. “NodeWrapper” object is used as a wrapper object to hold the previous processed node, the current node and the stack.

/**
  * An iterative solution for postorder traversal of a binary tree.
  * 
  * On a broad view, there are 2 cases that need to be covered in this algorithm
  * 1) If the current node is the parent of the previously processed node (the previously processed node could either be a 
  *   left or right child) then it means we are going up the tree. That in turn means we have already processed the child 
  *  sub-trees of the current node. So, it’s time to process the parent node and go for the next element in the stack.
  * 2) The other situations could be: 
  *  a) The current node can be the left or right child of the previously processed node. In this case, we are going down the tree. 
  *  b) The current node is the root node. 
  *  c) The current node can be the right companion of the previously processed node. 
  *  For all the above usecases, we call the special private method “navigateAndProcessNodesInPostOrder” method. 
  *  navigateAndProcessNodesInPostOrder  method takes care of pushing the current node, left child and right child (in that order) 
  *  to stack if the nodes exist. After pushing the nodes, it navigates to the left child (if it exists) because precedence is given 
  *  to the left node. If not it tries to navigate to the right child. If there are no child nodes then this method just processes 
  *  it without the need of adding that to stack because it’s a leaf node. “NodeWrapper” object is used as a wrapper object to hold 
  *  the previous processed node, the current node and the stack.
  * @param node Node Object
  * 
  */
 public void postOrderTraversalIterative(Node node) {
  if (node == null) {
   return;
  }
  
  Stack<Node> stack = new Stack<Node>();
  stack.push(node);
  Node prevNode = null;
  Node currNode = null;
  
  while (!stack.isEmpty()) {
   currNode = stack.pop();
   
   if (currNode.getLeft() == prevNode || currNode.getRight() == prevNode) {
    // If the current node is the parent of previously processed node. Navigating up the tree. So its enough just to process the node
    System.out.println(currNode);
    prevNode = currNode;
   } else {
    // If previously processed node was the parent of current node. i.e currently processing either the left or right child (navigating down).
    // If the node is the root node.
    // If the current node is the leaf node of a sub-tree. In this case previously processed node and current node are same.
    // If the current node being processed is the right companion of the previously processed node
    
    NodeWrapper nodeWrapper = new NodeWrapper(prevNode, currNode, stack);
    nodeWrapper = navigateAndProcessNodesInPostOrder(nodeWrapper);
    prevNode = nodeWrapper.getPrevNode();
    currNode = nodeWrapper.getCurrNode();
    stack = nodeWrapper.getStack();
   }
  }
 }
 
 /**
  * A helper method for post-order traversal - if given a node, it traverses and processes the sub-tree
  * NodeWrapper object is used to exchange prev, curr nodes and stack between the calling and called method
  * @param nodeWrapper
  * @return
  */
 private NodeWrapper navigateAndProcessNodesInPostOrder(NodeWrapper nodeWrapper) {
  Node currNode = nodeWrapper.getCurrNode();
  Node prevNode = nodeWrapper.getPrevNode();
  Stack<Node> stack = nodeWrapper.getStack();
  
  Node leftNode = currNode.getLeft();
  Node rightNode = currNode.getRight();
  if (leftNode != null  || rightNode != null) {
   // current node (if its a parent) is the last to be processed and so it has to be pushed to stack first
   stack.push(currNode);
   if (rightNode != null) {
    // If there is a right node, push it to stack
    stack.push(rightNode);
   }
   // If there is a left node, push it to stack
   if (leftNode != null) {
    stack.push(leftNode);
   }
   prevNode = currNode;
   
   // Left takes precedence. If there is a left node, go left else go right 
   if (leftNode != null) {
    currNode = currNode.getLeft();
   } else if (rightNode != null) {
    currNode = currNode.getRight();
   }
  } else { // its a leaf node, so process it
   System.out.println(currNode);
   prevNode = currNode;
  }
  nodeWrapper.setPrevNode(prevNode);
  nodeWrapper.setCurrNode(currNode);
  return nodeWrapper;
 }
 
  /**
  * An inner class NodeWrapper to encompass prevNode, currNode and stack for post-order traversal
  *
  */
 class NodeWrapper {
  private Node prevNode;
  private Node currNode;
  private Stack<Node> stack;
  
  NodeWrapper(Node prevNode, Node currNode, Stack<Node> stack) {
   this.prevNode = prevNode;
   this.currNode = currNode;
   this.stack = stack;
  }

  private Node getPrevNode() {
   return prevNode;
  }

  private Node getCurrNode() {
   return currNode;
  }

  private Stack<Node> getStack() {
   return stack;
  }

  private void setPrevNode(Node prevNode) {
   this.prevNode = prevNode;
  }

  private void setCurrNode(Node currNode) {
   this.currNode = currNode;
  }

  private void setStack(Stack<Node> stack) {
   this.stack = stack;
  }
  
 }

The entire code base for this project can be accessed from my Github repository – Binary Tree Traversal algorithms. I have added as many comments as possible in the code. Hope it will help everyone!!