Member-only story
Inorder Traversal (DFS) using Constant Space 😍 instead of O(height) 💩
This is a coding interview problem that Palantir asked.
Description
"Given a binary tree, perform an inorder traversal without using the normal O(height) space complexity approach. Do it using O(1) space."
Many of us are aware of two methods for the inorder traversal of a tree.
- Recursion: Uses O(h) space in the call stack.
- Iterative: Uses a stack to keep track of the path from the current node to root, which can grow up to the tree's height.
Why do we need space for this problem?
The critical thing to ask yourself is, why were we using any space?
And the answer is, we need space to save a node to come back to it after traversing its left subtree.
Be it stack or recursion, we process a subtree and, using pop in a stack or returning from a recursive call, reach to its parent and traverse the right subtree.
It means if we can somehow move from the last node of a left subtree (rightmost child) to the parent, then we will not need to save the parent.
