Increasing Order Search Tree — LeetCode 897 Inorder Rewire in O(n)

Problem Statement#

Given the root of a binary search tree, rearrange the tree in inorder so that the leftmost node is the new root and every node has no left child and only one right child.

Constraints:

• Number of nodes is in [1, 100].
• 0 <= Node.val <= 1000.
• The output must be a strictly right-skewed tree (a list-like tree).

Input:  root = [5,3,6,2,4,null,8,1,null,null,null,7,9]
Output: [1,null,2,null,3,null,4,null,5,null,6,null,7,null,8,null,9]

Why This Problem Matters#

LeetCode 897 "Increasing Order Search Tree" is a beloved interview easy at Facebook and LinkedIn because it tests a clean understanding of inorder traversal. The naive solution flattens to a list and rebuilds, which is O(n) extra space. The slick solution rewires pointers during a single inorder pass, demonstrating fluency with tree iteration.

The Core Insight#

Inorder traversal of a BST visits nodes in ascending value order. Maintain a moving pointer prev that always points to the last node attached to the result. When you visit a node during inorder, set node.left = None and prev.right = node, then advance prev = node. A dummy node simplifies handling the very first node.

Visual Dry Run#

BST [2,1,3]. Inorder visits 1, then 2, then 3.

Result chain: dummy -> 1 -> 2 -> 3, return dummy.right.

Solution (Optimal)#

class Solution:
    def increasingBST(self, root):
        dummy = TreeNode(0)
        self.prev = dummy
        def inorder(node):
            if not node:
                return
            inorder(node.left)
            node.left = None
            self.prev.right = node
            self.prev = node
            inorder(node.right)
        inorder(root)
        return dummy.right

var increasingBST = function(root) {
    const dummy = new TreeNode(0);
    let prev = dummy;
    const inorder = (node) => {
        if (!node) return;
        inorder(node.left);
        node.left = null;
        prev.right = node;
        prev = node;
        inorder(node.right);
    };
    inorder(root);
    return dummy.right;
};

Time: O(n) — each node visited once. Space: O(h) — recursion stack proportional to tree height.

Common Mistakes#

• Forgetting to set node.left = None before attaching, leaving stale left pointers.
• Returning the original root instead of dummy.right.
• Using a list-and-rebuild approach when interviewer wants in-place rewiring.
• Mutating during preorder or postorder instead of inorder, which produces wrong order.
• Mishandling the very first node by trying to special-case it instead of using a dummy.

Interview Tips#

• Mention that inorder of a BST yields sorted order — this earns instant credit.
• Bring up the dummy node trick as a clean way to avoid special-casing the head.
• For very deep trees, mention an iterative inorder with explicit stack.
• If asked, the same trick works to flatten any binary tree given a custom traversal order.

Follow-up Questions#

• Iterative version: convert to a stack-based inorder. Hint: classic explicit-stack pattern.
• Decreasing order tree: mirror by using reverse inorder. Hint: swap left and right.
• Doubly linked list: keep both prev and next pointers. Hint: also set node.left = prev.
• Stream multiple trees: chain them. Hint: keep a single global prev across trees.
• Morris-style: O(1) space variant. Hint: thread predecessor right pointers.

Key Takeaways#

• LeetCode 897 is a textbook inorder-rewire problem.
• Inorder of a BST visits values in sorted ascending order.
• Use a dummy node to avoid special-casing the head of the result.
• Set node.left = None and prev.right = node during the visit step.
• Time is O(n), space is O(h) for the recursion stack.
• Asked frequently at Facebook, LinkedIn, and Bloomberg.
• The dummy + prev pointer pattern reuses for "convert BST to doubly linked list".