The O(n) Club: Maximum Binary Tree: When Your Array Is a Bunch of Control Freaks

The O(n) Club: Maximum Binary Tree—When Your Array Is a Bunch of Control Freaks

⚡ TL;DR

Choice: scan for the max, crown it root, recursively slice left/right subarrays. It’s like quicksort, but the pivot refuses to be humble.

// Brute force: O(n²)
public TreeNode constructMaximumBinaryTree(int[] nums) {
    return build(nums, 0, nums.length - 1);
}
private TreeNode build(int[] nums, int left, int right) {
    if (left > right) return null;
    int maxIdx = left;
    for (int i = left; i <= right; i++) if (nums[i] > nums[maxIdx]) maxIdx = i;
    TreeNode root = new TreeNode(nums[maxIdx]);
    root.left = build(nums, left, maxIdx - 1);
    root.right = build(nums, maxIdx + 1, right);
    return root;
}

🧠 How Devs Usually Mess This Up

Welcome to a hall of fame built on classic rookie moves:

• Trying to make this a heap or BST problem. Don’t—there’s zero ordering, only pure, glorious max at every split.
• Allowing duplicates. Every value must be unique, per spec. Adding more drama with twins is unnecessary pain.
• Misplacing recursion. This is not “left-to-right construction.” Find the current max, split, then recurse on both halves like you mean it.
• Null negligence. If you forget to return null for empty slices, your next stack trace will be its own horror tree.

🔍 What’s Actually Going On

Your array is an insufferable reality competition: the largest contestant always seizes power. The others splinter to left/right side games, repeating the drama recursively.
Do not treat this like a heap or BST intervention. At every recursion: find the biggest, make it boss, let everyone else fight for subarray turf. (It’s basically quicksort if pivots were egomaniacs.)

🛠️ PseudoCode

• Base case: If subarray is empty, return null.
  

  if (left > right) return null;

  Don’t force destiny—empty sides need to be null or chaos reigns.
• Find the max element and its index in (left, right).
  

  int maxIdx = left;
  for (int i = left; i <= right; i++)
      if (nums[i] > nums[maxIdx]) maxIdx = i;

  Resist jumping to endpoints. Full scan every time.
• Create a new node with the max value.
  

  TreeNode root = new TreeNode(nums[maxIdx]);

  Boom. That’s your root.
• Recurse left and right, assign to root.
  

  root.left = build(nums, left, maxIdx - 1);
  root.right = build(nums, maxIdx + 1, right);

  You mess this up, your branches will haunt you.
• Return root.
  

  return root;

  Done on this split. Next!

💻 The Code

// TreeNode definition
class TreeNode {
    int val;
    TreeNode left, right;
    TreeNode(int x) { val = x; }
}
 public TreeNode constructMaximumBinaryTree(int[] nums) {
    return build(nums, 0, nums.length - 1);
}
private TreeNode build(int[] nums, int left, int right) {
    if (left > right) return null;
    int maxIdx = left;
    for (int i = left; i <= right; i++) if (nums[i] > nums[maxIdx]) maxIdx = i;
    TreeNode root = new TreeNode(nums[maxIdx]);
    root.left = build(nums, left, maxIdx - 1);
    root.right = build(nums, maxIdx + 1, right);
    return root;
}

⚠️ Pitfalls, Traps & Runtime Smacks

• Empty Slices: Return null or face the wild pointers.
• Duplicates: Leave them out—spec requires all values unique. If you add, have fun with ambiguous splits.
• Time & Space: O(n²) in the worst case (already sorted is doomsday). Yes, there’s a fancy O(n) stack trick, but recursion is interview gold.

🧠 Interviewer Brain-Tattoo

If you turn this into a heap or BST, you’re going to cry. Pick the max, split, repeat—it’s quicksort on ego steroids.