Increasing Order Search Tree: Flatten a BST with Inorder Traversal
You have a binary search tree, and you need to rearrange it so that every node only has a right child, and the nodes appear in increasing order. That is LeetCode 897: Increasing Order Search Tree, and once you see the connection to inorder traversal, the solution clicks into place.
The problem
Given the root of a binary search tree, rearrange the tree so that:
- The leftmost node becomes the new root.
- Every node has no left child and only one right child.
- The nodes are ordered by their values (which is the inorder traversal order for a BST).
The approach
Since a BST's inorder traversal produces values in sorted order, the key insight is: just do an inorder traversal and relink the nodes as you go. You create a dummy node to serve as the head of your new chain. As you visit each node during inorder traversal, you set prev.right = current_node, clear the current node's left pointer, and advance prev.
The recursive version is clean. You traverse left, process the current node (link it into the chain), then traverse right. After the traversal finishes, the dummy node's right child is the new root.
def increasingBST(root):
dummy = TreeNode(0)
prev = dummy
def inorder(node):
nonlocal prev
if not node:
return
inorder(node.left)
node.left = None
prev.right = node
prev = node
inorder(node.right)
inorder(root)
return dummy.right
Step-by-step walkthrough
Let's trace through a smaller BST to see how nodes get relinked one by one during the inorder traversal.
Step 1: Begin inorder traversal. Recurse left to node 1.
Inorder visits left subtree first. We go 5 -> 3 -> 1. Node 1 has no left child, so it is the first visited node. We set prev.right = 1 and advance prev.
Step 2: Return up. Visit node 3. Link 1.right = 3.
After finishing 1's left subtree (empty) and visiting 1, we return to 3. We set prev(1).right = 3, then set 3.left = null and advance prev to 3.
Step 3: Visit node 4 (right child of 3). Link 3.right = 4.
Node 3's right subtree has root 4. Node 4 has no children, so we visit it immediately. Set prev(3).right = 4 and advance prev to 4.
Step 4: Return to root node 5. Visit it. Link 4.right = 5.
Left subtree of 5 is fully processed. Now visit node 5. Set prev(4).right = 5, clear 5.left, and advance prev to 5.
Step 5: Visit node 6. Link 5.right = 6. Traversal complete.
Node 6 has no children, so we visit it and link prev(5).right = 6. The dummy node's right child points to 1, which is the new root of the right-only chain.
Each time we visit a node, we attach it to prev.right, clear its left pointer, and move prev forward. By the end of the traversal, the dummy node's right child points to the smallest value, and every subsequent node hangs off the right pointer of the one before it.
Complexity analysis
| Metric | Value |
|---|---|
| Time | O(n) |
| Space | O(h) where h is tree height |
Time: We visit every node exactly once during the inorder traversal, so the total work is O(n).
Space: The recursion stack goes as deep as the tree height. For a balanced BST that is O(log n), but for a skewed tree it could be O(n). You can also solve this iteratively using Morris traversal for O(1) extra space, though the recursive version is easier to get right in an interview.
The building blocks
Inorder traversal
Inorder traversal visits left, root, right. For a BST, this produces nodes in sorted order. Recognizing that "sorted order" and "inorder traversal" are the same thing for BSTs is the core insight here. Once you see that, the problem reduces to "do an inorder traversal and build a linked list along the way."
Dummy node technique
Using a dummy (sentinel) node as the starting point of your result chain simplifies the logic. Without it, you would need a special case for the first node. With the dummy, every node including the first gets attached the same way: prev.right = node. At the end, you just return dummy.right.
Edge cases
- Single node: The tree is already a valid right-only chain. The traversal visits one node and returns it.
- Already right-skewed: If every node only has a right child, inorder traversal walks straight down the right side, and the relinking is a no-op.
- Left-skewed tree: Every node only has a left child. Inorder traversal visits them from the bottom up, and each one gets relinked to the right. This is where the recursion depth is O(n).
- Empty tree (
root is None): Return None immediately. The inorder function never executes.
From understanding to recall
You just watched the inorder traversal relink nodes into a right-only chain, step by step. The pattern is simple: traverse left, visit the node (attach it to the chain and clear its left pointer), traverse right. But could you write it from scratch without looking? The dummy node trick, the prev pointer, clearing node.left before moving on... these small details are easy to forget under pressure. Spaced repetition helps you internalize them so they come back automatically when you need them.
Related posts
- Binary Tree Inorder Traversal - The foundational traversal pattern that powers this solution
- Flatten Binary Tree to Linked List - A similar rearrangement problem using preorder instead of inorder
- Convert Sorted Array to Binary Search Tree - The reverse direction: building a balanced BST from sorted data