🙏

জয়  শ্রী  রাম

🕉

---

I would ask all the readers to give this chapter a special attention since if you have a strong grasp of the concept being introduced here, you would be able to think through and have an optimized O(n), where n is the total number of nodes present in the tree, solution for even a complex tree traversal problems in just few minutes.

We all know about the three types of DFS traversal in Binary Trees: Preorder, Inorder and Postorder. After reading this entire article, you will start appreciating the potential of the iterative implementations of Inorder Binary traversals as to how many different kinds of amazing and complex Binary Tree related problems you can solve so easily with them.
The reason for emphasizing on the iterative implementation is that we, in most cases, use recursive implementation of the Binary Tree DFS traversals to solve Binary Tree traversal problems, but I want to show how the iterative implementations of these traversals make our lives easier to solve problems. After you are done reading and assimilating this article you would have a whole different perspective on how to go about solving most Binary Tree related problems, and will make even some of the hardest Binary Tree problems seem easy.

Iterative Implementation:

Now that we know how the Binary Tree traversal works, let's look at the iterative algorithms for all of these traversals.

Inorder Traversal

Iterative Algorithm:

Let's revisit how inorder traversal works:

• We traverse all the way to the left till the left-most node (i.e, the childNode of the with both childNodes as null)
  So we are looking at something like:

  
              while (root != null) {
                  stack.push(root);
                  root = root.left;
              }
          

• Once we are at the left most node, we process it.

          
                  // visit
                  root = stack.pop();
                  // process
                  res.add(root.val); //let's suppose we would just have to store it in an output list in inorder
              
  

• Now that currentNode is processed visit its right childNode.
  root = root.right;
• Repeat the above three steps as long as stack is non-empty or current node is not null
  

  
      while (!stack.isEmpty() || root != null) { // root is current Node here
      }
  
  

Now let's implement the algorithm:

Java code:

public List<Integer> inorderIterative(Node root) {
    List<Integer> res = new ArrayList<>();
    if (root == null) {
        return res;
    }
    Deque<Node> stack = new ArrayDeque<>();
    while(!stack.isEmpty() || root != null) {
        while (root != null) {
            stack.push(root);
            root = root.left;
        }
        // visit
        root = stack.pop();
        // process
        res.add(root.val);

        root = root.right;
    }

    return res;
}

Python Code:



Login to Access Content

Applications of Iterative Inorder Traversal Algorithm:

• Kth smallest element in a Binary Search Tree
  
  Java code:
  
  
  
  Login to Access Content
  
  
  
  
  Python Code:
  
  
  
  Login to Access Content
  
  
  
• Validate whether a Binary Tree is Binary Search Tree
  
  Java code:
  
  
  
  Login to Access Content
  
  
  
  
  Python Code:
  
  
  
  Login to Access Content
  
  
  
• Convert Binary Search Tree to Sorted Doubly Linked List IN PLACE
  The left child and right child pointers in the BST are synonymous to the previous and next pointers in a doubly-linked list. For a circular doubly linked list, the previous node of the first element is the last element, and the next node of the last element is the first element.
  We want to do the transformation in place. After the transformation, the left pointer of the tree node should point to its previous node, and the right pointer should point to its next node. You should return the pointer to the smallest element of the linked list.
  
  Solution: So basically we need to do an inorder traversal and at the end the leftChild pointer of each node should point to the previous node in the inorder traversal list, and rightChild should point to the node right next to it after inorder traversal.
  
  Java Code:
  
  
  
  Login to Access Content
  
  
  
  
  Python Code:
  
  
  
  Login to Access Content
  
  
  
  
  Now let's see how the recursive solution would look like:
  
  Java code:
  
  

  
  class Solution {
      Node first = null;
      Node last = null;
      public Node treeToDoublyList(Node root) {
          if (root == null) {
              return null;
          }
          helper(root);
          first.left = last;
          last.right = first;
          
          return first;
      }
      
      private void helper(Node root) {
          if (root.left != null) {
              helper(root.left);
          }
  
          // begin: visit and process 
          if (first == null) {
              first = root;
          } 
          else {
              last.right = root;
              root.left = last;
          }
      
          last = root;
          // end: visit and process
  
          if (root.right != null) {
              helper(root.right);
          }
      }
  }
        
  

  
  
  Python Code:
  
  
  
  Login to Access Content
  
  
  

Must Read Chapters:

• Iterative Preorder Traversal
• Iterative Postorder Traversal
• Iterative Postorder Traversal
  w/ Single Stack
• How to track traversed paths in DFS

Instructor: