Leetcode Pattern 0 | Iterative traversals on Trees

The key to solve algorithm problems posed in technical interviews or elsewhere is to quickly identify the underlying patterns. This is my attempt to decompose leetcode problems and group them into minimal sets. I figured out this would be a useful insight for future people in tech ( long live whiteboards !) to actually write a series of short blog posts.

Here I present one such powerful pattern related to trees and present 3 different problems that can be solved using this pattern. Whenever you solve a tree problem using recursion, always follow it up writing an iterative solution and vice-versa.

Iterative solutions help us really understand what is going on while recursion is concise and beautiful, we need to be able to write both in order to become good programmers.

An iterative in-order traversal using stack to solve multiple tree problems:

Inorder Traversal of Binary Tree

Validate if Tree is a BST

For a binary tree to be a BST, the inorder has to be in sorted (ascending) order.

Kth Smallest element in BST

Inorder traversal of a BST gives us a sorted order of the items in it. So a simple inorder breaking off at the kth item would give us our answer !

Try doing this for preorder and postorder too and see how many new problems you would have unlocked ! ( Share your solutions in the comments )

I am also going to translate the solutions into Java and Python as I progress, feel free to contribute back by sharing your own patterns or translating code into your favorite language of choice.

Also feel free to connect with me on LI : https://www.linkedin.com/in/sourabh-reddy/