Powerful Iterative Approach for Inorder Traversal
Get startedজয় শ্রী রাম
🕉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
Pay special attention to the following Iterative Inorder Traversal Implementation. This is one not as trivial as the other two
iterative algorithm. Iterative inorder algorithm will come handy in solving many complex Tree problems.
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 }
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
I prefer not to take Stack Java class. You almost never see a developer using Stack class in production level code.
In production grade code you would see the use of Deque. Deque interface has all the methods you need to use it as a Stack or
Queue as your need may be.
Remember one thing, what makes you stand out from the crowd in your coding interview is your ability to write Production Grade code. Make it your second nature. This may seem like a small thing, but it is not. It matters.
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
Basically the challenge would be to first figure out if you need to do preorder, inorder or postorder traversal as part of your
solution for a problem. Once you have figured that out, just try to think the traversal in the iterative way. After you
have come up with the logic you need to implement for each visited node, simply write the iterative program, and
put the logic after you are visiting the current node, where you are actually processing the node. It's that simple.
As you try to solve more and more tree traversal problems using iterative approach you would find that
in most cases thinking in the iterative way feels much more natural, intuitive and easier.
Must Read Chapters:
- Iterative Preorder Traversal
- Iterative Postorder Traversal
-
Iterative Postorder Traversal
w/ Single Stack - How to track traversed paths in DFS