The O(n) Club: Constructing BST from Preorder — Recursion, Not Regret

The O(n) Club: Constructing BST from Preorder — Recursion, Not Regret

⚡ TL;DR

Rebuild a Binary Search Tree from an array that screams “preorder!” (root, left, right). The brute force way? Insert each value, one limp node at a time. Feels about as efficient as writing Java with oven mitts. The enlightened path? Recursively build using boundaries for each node so you don’t repaint the Sistine Chapel for every child.

// Brute force (prepare tissues for sorted input):
TreeNode root = null;
for (int val : preorder) root = insert(root, val);

🧠 How Devs Usually Mess This Up

Most devs treat the preorder like a buffet: just slap values onto the tree as they show up. The problem? Insert-one-by-one nukes your runtime on sorted arrays (hello, O(n²)). Others channel their inner chef and split arrays for “left” and “right” children at every call, blowing up memory and time like a poorly-planned bake sale. And let’s not forget The Scanners—folks who re-traverse subarrays just to find split points. No thanks, I’d rather debug CSS.

🔍 What’s Actually Going On

Preorder means every value knows where it stands: root first, then its hopeful left descendants, then the right. In a BST, every left child is less than root, every right is greater. So, when constructing, just keep everyone in their lane. Pass upper and lower bounds as you recurse—kids who don’t play nice with those rules are skipped. You only need a single index to stroll down the preorder array, no subarrays or split-the-bill drama.

🛠️ PseudoCode

• Start at index 0
  

  int idx = 0;

  Track where you are. No off-by-one party fouls.
• Recursive method with bounds
  

  TreeNode helper(int lower, int upper)

  Accepts only those values that fit between lower & upper. Code doesn’t lie, boundaries never cheat.
• Base case
  Out of bounds or out of input? Return null. Tree construction is over sooner than your last relationship.
• Create the node
  

  int val = preorder[idx++];
  TreeNode node = new TreeNode(val);

• Left child
  

  node.left = helper(lower, val - 1);

  Everything less than your root, forever loyal.
• Right child
  

  node.right = helper(val + 1, upper);

  Everything greater, looking to the future.
• Return node
  You’re done here, boss.

💻 The Code

// Definition for a binary tree node.
class TreeNode {
    int val;
    TreeNode left, right;
    TreeNode(int x) { val = x; }
}
 public class Solution {
    private int idx = 0;
    public TreeNode bstFromPreorder(int[] preorder) {
        return helper(preorder, Integer.MIN_VALUE, Integer.MAX_VALUE);
    }
     private TreeNode helper(int[] preorder, int lower, int upper) {
        if (idx == preorder.length) return null;
        int val = preorder[idx];
        if (val < lower || val > upper) return null;
        idx++;
        TreeNode root = new TreeNode(val);
        root.left = helper(preorder, lower, val - 1);
        root.right = helper(preorder, val + 1, upper);
        return root;
    }
}

⚠️ Pitfalls, Traps & Runtime Smacks

• Sorted preorder: Converts your tree to a sad linked list. O(n²) if you use the naive insert.
• Repeated values: Not allowed. Your BST will combust. Unique values only, please.
• Stack limits: Java’s fine, but watch for StackOverflows if your BST is tall and proud. (Recursion ain’t free!)
• Complexity: Real solution is O(n) time, O(h) space (h = tree height, aka nap risk).

🧠 Interviewer Brain-Tattoo

Bounds > splits. When you carry just one index and tight boundaries, you look smarter than the brute forces and never once slice an array. Now go make your future self proud.