One common interview problem that commonly gets asked by interviewer is to write an in-order binary tree traversal algorithm. This deceptively simple problem in my own opinion is harder than it looks like. Although the recursive version is tidier, it hides the complexity that goes behind it. I, too, ended up memorizing those three lines, only to later realize that sometimes it was much harder to come up with a solution to a problem based on in-order traversal only using recursion.
Inorder Binary Search Tree Traversal
Recall our good ol’ recursive in-order traversal.
Like a compiler, we can mechanically convert our function calls to use an explicit stack, but readibility/memoribility would suffer.
The in-order traversal requires that we print the leftmost node first and the right most node at the end. So basically for each node we need to go as far as down and left as possible. So the line
inorder(root->left) could be replaced with a while loop to have similar effect.
Now we need to retrieve the top node and store it’s right child if it exists
An iterative solution can help us solve multiple tree problems, and the same template could be used for multiple problems.
Let’s use the same template we created earlier to solve multiple leetcode problem using the same pattern
For leetcode problem Binary Tree Inorder Traversal, we need to return a list of node so rather than printing. This could be solved by storing the values in a list and returning it.
Similarly, in order to Validate Binary Search Tree could be solved by verifying if the in-order traversal is in ascending order
Find Kth Smallest Element in a BST by simply breaking at kth element
Search in a Binary Search Tree becomes much simpler and one needs to simply check for
val you are looking for.
Increasing Order Search Tree has similar intuition. Each time we meet a node, link it like a linked list using the right pointer. To facilitate the linking, create a dummy head
For Recover Binary Search Tree, the question boils down to to find “2” elements in a given sorted arrangement , such that both of these elements violate the “sorted” order, and swap them back to their original places.
For Convert BST to Greater Tree, The solution is the modification of inorder travel. Namely, travel right subtree, change the root value, and travel left subtree.
Once you have realized the pattern, you could see Binary Search Tree Iterator problem has the exact same structure
- Some initialization.
- A while-loop with a condition that tells whether there is more.
- The loop body gets the next value and does something with it.
That’s it! I hope you enjoyed the explanation, not only we managed to understand inorder binary search tree traversal but also managed to solve handful leetcode problems as well and feel free to reach out to me on how I could improve its clarity. Next great steps after you think you’ve understood this is to try and implement the iterative solutions for preorder binary tree traversal and postorder binary tree traversal!