Maximum Binary Tree - Video Solutions

Problem Overview: Given an integer array with no duplicates, construct a binary tree where the root is the maximum value in the array. The left subtree is built from elements left of the maximum, and the right subtree from elements on the right. This recursive definition creates what’s called a Maximum Binary Tree.

Approach 1: Recursive Division (Divide and Conquer) (Time: O(n^2) worst, Space: O(n))

The definition of the tree directly suggests a divide and conquer strategy. Scan the current subarray to find the maximum element. Create a node with that value, then recursively build the left subtree from elements before the maximum and the right subtree from elements after it. Each recursive call reduces the problem size until the subarray becomes empty. The drawback is that finding the maximum requires a full scan each time, which leads to O(n^2) time when the array is sorted in decreasing or increasing order. Space complexity is O(n) due to recursion depth and the tree structure.

Approach 2: Monotonic Stack (Time: O(n), Space: O(n))

A more efficient approach uses a monotonic stack. Iterate through the array and maintain a decreasing stack of tree nodes. For each new value, create a node and pop all smaller nodes from the stack. The last popped node becomes the left child of the current node because it is the largest smaller element to its left. If the stack still contains elements, the top node becomes the parent and the current node becomes its right child. Push the current node onto the stack and continue. Each element is pushed and popped at most once, giving linear O(n) time. The stack stores at most n nodes, so space complexity is O(n). This approach constructs the same binary tree without repeatedly scanning subarrays.

Recommended for interviews: Interviewers usually expect the monotonic stack solution because it reduces the naive recursive O(n^2) approach to optimal O(n). Starting with the recursive definition demonstrates understanding of the problem structure, then optimizing with a monotonic stack shows algorithmic maturity and familiarity with common stack patterns.