Increasing Order Search Tree

easy binary tree bst in-order traversal

Problem

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

Inputroot = [5, 3, 6, 2, 4, null, 8, 1]

Output[1, null, 2, null, 3, null, 4, null, 5, null, 6, null, 8]

The in-order sequence is 1, 2, 3, 4, 5, 6, 8. Each value becomes a right child of the previous one, forming a right-leaning chain.

tree (level-order, use "null" for gaps)

def increasingBST(root):
    dummy = TreeNode()
    cur = dummy
    def inorder(node):
        nonlocal cur
        if not node:
            return
        inorder(node.left)
        node.left = None
        cur.right = node
        cur = node
        inorder(node.right)
    inorder(root)
    return dummy.right

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

class Solution {
    private TreeNode cur;
    public TreeNode increasingBST(TreeNode root) {
        TreeNode dummy = new TreeNode();
        cur = dummy;
        inorder(root);
        return dummy.right;
    }
    private void inorder(TreeNode node) {
        if (node == null) return;
        inorder(node.left);
        node.left = null;
        cur.right = node;
        cur = node;
        inorder(node.right);
    }
}

class Solution {
    TreeNode* cur;
    void inorder(TreeNode* node) {
        if (!node) return;
        inorder(node->left);
        node->left = nullptr;
        cur->right = node;
        cur = node;
        inorder(node->right);
    }
public:
    TreeNode* increasingBST(TreeNode* root) {
        TreeNode dummy;
        cur = &dummy;
        inorder(root);
        return dummy.right;
    }
};

Explanation

We need to rebuild the BST as a chain that leans entirely to the right, with values in increasing order. The key fact is that an inorder traversal of a BST visits values from smallest to largest, which is exactly the order we want the chain in.

To stitch the chain together cleanly, we use a dummy head node and a moving cur pointer that always points at the tail of the chain built so far. Starting cur at the dummy means we never have to special-case the first node.

During the inorder walk, when we reach a node we do three things: clear node.left = None (no left children allowed), attach it with cur.right = node, and advance cur = node. The node becomes the new tail.

Example: root = [5,3,6,2,4,null,8,1]. Inorder yields 1,2,3,4,5,6,8. We hang 1 off the dummy, then 2 to the right of 1, then 3, and so on, producing a right-only chain 1 → 2 → 3 → 4 → 5 → 6 → 8.

At the end we return dummy.right, the real head of the chain. Each node is handled once, so this is O(n) time.

Time: O(n) Space: O(h)