Increasing Order Search Tree - Video Solutions

Problem Overview: You are given the root of a Binary Search Tree. The goal is to rearrange the tree so that it becomes an increasing order tree where every node has no left child and only one right child. The resulting structure should follow the in-order sequence of the original BST.

Approach 1: In-Order Traversal with Recursion (Time: O(n), Space: O(h))

A Binary Search Tree naturally produces values in sorted order when traversed using in-order traversal. That property makes this problem straightforward: perform an in-order traversal and rebuild the tree while visiting nodes. Maintain a dummy node and a pointer called current. Each time you visit a node, set node.left = null, attach it to current.right, and move the pointer forward.

This approach uses recursion to traverse the tree depth-first, which implicitly uses the call stack. The recursion depth is proportional to the tree height h. For balanced trees this is O(log n), but in the worst case (skewed tree) it becomes O(n). The algorithm touches each node exactly once, so the time complexity remains O(n).

This method is easy to reason about and commonly used in interviews. It relies on the classic Depth-First Search traversal pattern and works well when recursion is acceptable.

Approach 2: Morris In-Order Traversal (Time: O(n), Space: O(1))

Morris traversal performs in-order traversal without recursion or an explicit stack. Instead, it temporarily modifies the tree by creating threaded links between nodes. For each node, find its inorder predecessor in the left subtree. If the predecessor's right pointer is null, create a temporary link back to the current node and move left. If the link already exists, remove it, process the node, and move right.

While visiting nodes in sorted order, restructure the tree the same way as the recursive solution: set left = null and attach nodes sequentially using a running pointer. Because Morris traversal eliminates recursion and auxiliary stacks, the extra space usage becomes O(1).

The tradeoff is implementation complexity. Morris traversal requires careful pointer manipulation and temporary structural changes, which can introduce bugs if handled incorrectly. However, it is valuable when memory constraints matter or when interviewers specifically ask for constant extra space.

Recommended for interviews: Start with the recursive in-order traversal. It clearly demonstrates your understanding of BST ordering and DFS traversal. After presenting the O(n) time, O(h) space solution, mention Morris traversal as the optimized follow-up that reduces space to O(1). Interviewers usually expect the recursive solution first, while the Morris version shows deeper understanding of tree traversal techniques.