The O(n) Club: Increasing Order Search Tree: When Your BST Just Wants to Be a Queue

The O(n) Club: Increasing Order Search Tree—When Your BST Just Wants to Be a Queue

⚡ TL;DR

If your BST refuses to queue up nicely, tell it: in-order traversal is your friend. Snip left pointers, daisy-chain on the right, and embrace single-file minimalism. Fastest Java fix?

// In-order and right-link transformation
TreeNode prev = new TreeNode(-1);
TreeNode dummy = prev;
inOrder(root);
return dummy.right;
 void inOrder(TreeNode node) {
    if (node == null) return;
    inOrder(node.left);
    prev.right = node;
    node.left = null;
    prev = node;
    inOrder(node.right);
}

🧠 How Devs Usually Mess This Up

Some classics from the “how did I end up with a forest instead of a straight tree?” department:

• Collection obsession: Grab every value in a list, then burn and rebuild the tree from scratch. Way to double (or triple) your memory bill for zero interviewer points!
• Re-inventing TreeNodes: Nothing says “I missed the point” like needlessly allocating new nodes when you could just re-thread the old ones.
• BST blind spot: Thinking any tree will behave—in a non-BST, in-order means pure chaos, not sorted order.
• Left-pointer laziness: Forgetting to sever .left dooms you to infinite loops or memory leaks. Enjoy that debugging spiral.

🔍 What’s Actually Going On

Picture your BST like cats at feeding time. You want them to line up, smallest first, each patiently tapping the right shoulder of the next. That’s in-order traversal: left (smallest), root (medium), right (largest). At each stop, you assign the next spot to the right, snip the left to avoid feline rebellion, and repeat until everyone’s purring in order.

🛠️ PseudoCode

• Start with a Dummy Node:
  TreeNode dummy = new TreeNode(-1); – this one just handles introductions.
• Track the Tail:
  TreeNode prev = dummy; – think of prev as your end-of-line monitor.
• Traverse In-Order:
  inOrder(root); – visit everyone from smallest left to biggest right.
• At Each Visit:
  • Chain prev.right to node
  • Nullify node.left to avoid backwards chaos
  • Hop prev up to the new node

  prev.right = node;
  node.left = null;
  prev = node;

• Return dummy.right after traversal—it’s your new queue leader.

💻 The Code

// Definition for a binary tree node.
class TreeNode {
    int val;
    TreeNode left;
    TreeNode right;
    TreeNode(int x) { val = x; }
}
 class Solution {
    private TreeNode prev;
    public TreeNode increasingBST(TreeNode root) {
        TreeNode dummy = new TreeNode(-1);
        prev = dummy;
        inOrder(root);
        return dummy.right;
    }
    
    private void inOrder(TreeNode node) {
        if (node == null) return;
        inOrder(node.left);
        prev.right = node;
        node.left = null;
        prev = node;
        inOrder(node.right);
    }
}

⚠️ Pitfalls, Traps & Runtime Smacks

• Left pointer neglect: Miss one node.left = null, and the next thing you debug is your own patience.
• BST imposters: This strategy falls apart for trees that aren’t BSTs—in-order may look like the sorting hat had a meltdown.
• Risky global state: That prev variable? Fine here, but don’t share it between threads or recursion sets, or chaos ensues.
• Runtime wisdom: O(n) time, O(h) space for stack—h is the height, not how deep your coffee cup goes.

🧠 Interviewer Brain-Tattoo

“A right-skewed BST is nature’s way of reminding you: sometimes all the lefts just need to be null and out of your life.”