Maximum Binary Tree

Problem

You are given an integer array nums with no duplicates. A maximum binary tree can be built recursively from nums using the following algorithm:

1. Create a root node whose value is the maximum value in nums.
2. Recursively build the left subtree on the subarray prefix to the left of the maximum value.
3. Recursively build the right subtree on the subarray suffix to the right of the maximum value.

Return the maximum binary tree built from nums.

Examples

Example 1:

graph TD;
	F(6) --- C(3) & E(5)
	C ~~~ N1:::hidden
	C --- B(2)
	B ~~~ N2:::hidden
	B --- A(1)
	E --- G(0)
	E ~~~ N3:::hidden	
	
classDef hidden display:none

Input: nums = [3,2,1,6,0,5]
Output: [6,3,5,null,2,0,null,null,1]
Explanation: The recursive calls are as follow:
- The largest value in [3,2,1,6,0,5] is 6. Left prefix is [3,2,1] and right suffix is [0,5].
    - The largest value in [3,2,1] is 3. Left prefix is [] and right suffix is [2,1].
        - Empty array, so no child.
        - The largest value in [2,1] is 2. Left prefix is [] and right suffix is [1].
            - Empty array, so no child.
            - Only one element, so child is a node with value 1.
    - The largest value in [0,5] is 5. Left prefix is [0] and right suffix is [].
        - Only one element, so child is a node with value 0.
        - Empty array, so no child.

Example 2:

Tree = 
    3
     \ 
      2 
       \
         1

Input: nums = [3,2,1]
Output: [3,null,2,null,1]

Solution

Method 1 - Recursion and Brute Force

Code

Java

class Solution {
    public TreeNode constructMaximumBinaryTree(int[] nums) {
        return buildTree(nums, 0, nums.length);
    }

    private TreeNode buildTree(int[] nums, int start, int end) {
        if (start >= end) {
            return null;
        }

        // Find the maximum value and its index
        int maxIdx = start;
        for (int i = start; i < end; i++) {
            if (nums[i] > nums[maxIdx]) {
                maxIdx = i;
            }
        }

        // Create the root node
        TreeNode root = new TreeNode(nums[maxIdx]);

        // Recursively build the left and right subtrees
        root.left = buildTree(nums, start, maxIdx);
        root.right = buildTree(nums, maxIdx + 1, end);

        return root;
    }
}

Python

class Solution:
    def constructMaximumBinaryTree(self, nums: List[int]) -> Optional[TreeNode]:
        if not nums:
            return None

        # Find the maximum value and its index
        max_val = max(nums)
        max_idx = nums.index(max_val)

        # Create the root node
        root = TreeNode(max_val)

        # Recursively construct the left and right subtrees
        root.left = self.constructMaximumBinaryTree(nums[:max_idx])
        root.right = self.constructMaximumBinaryTree(nums[max_idx + 1:])

        return root

Complexity

• ⏰ Time complexity: O(n^2). The recursive function finds the maximum element for each subarray, which takes O(n) per level of recursion. In the worst case (when the array is sorted in descending or ascending order), this results in O(n^2).
• 🧺 Space complexity: O(n). Space is used for the recursive stack, which can go as deep as O(n) in the worst case. Additionally, space is used for storing the tree nodes, i.e., O(n). Hence overall space complexity is O(n).

Method 2 - Using Monotonic Decreasing Stack

When constructing the tree, the maximum value is kept as the root. Values smaller than the maximum and to the left are added to the left subtree, while values smaller than the maximum and to the right form the right subtree.

A monotonic decreasing stack can be used for this purpose. With a decreasing stack:

1. While pushing a number i, during the popping process, the last popped element becomes the left child of i.
2. If an element remains on the stack after popping, it represents a value larger than i. Hence, i becomes a candidate for this element's right subtree, though it might not always be the final right child.

For e.g., given nums = [3, 1, 2], first 3 is processed and pushed onto the stack. Next, 1 is pushed, becoming the candidate for node(3).right. When 2 is processed, 1 is popped, making node(2).left = node(1). Then 2 is pushed and assigned as node(3).right. The correct tree structure is achieved.

Algorithm

1. Traverse the array, creating nodes sequentially and maintaining a decreasing sequence in the stack.
2. For each new node:
   • Pop elements from the stack while their value is smaller than that of the current node. The last popped node becomes the left child of the current node (curNode.left = last popped node).
   • After the popping process, the top of the stack remains larger, making it the root of the current node (peek.right = curNode).
3. At the end, return the base node of the stack.

Code

Java

class Solution {
    public TreeNode constructMaximumBinaryTree(int[] nums) {
        Stack<TreeNode> stack = new Stack<>();

        for (int n : nums) {
            TreeNode curNode = new TreeNode(n);

            // Assign left children via popping
            while (!stack.isEmpty() && stack.peek().val < curNode.val) {
                curNode.left = stack.pop();
            }

            // Link current node as the right child of the top node in the stack
            if (!stack.isEmpty()) {
                stack.peek().right = curNode;
            }

            // Push current node onto the stack
            stack.push(curNode);
        }

        // Return the node at the bottom of the stack (root of the constructed tree)
        return stack.get(0);
    }
}

Python

class Solution:
    def constructMaximumBinaryTree(self, nums: List[int]) -> Optional[TreeNode]:
        stack = []

        for n in nums:
            cur_node = TreeNode(n)

            # Assign left children
            while stack and stack[-1].val < cur_node.val:
                cur_node.left = stack.pop()
            
            # Link current node to the previous node in stack as its right child
            if stack:
                stack[-1].right = cur_node
            
            # Push the current node onto the stack
            stack.append(cur_node)
        
        # Return the bottom-most node in the stack (represents the root)
        return stack[0]

Complexity

• ⏰ Time complexity: O(n). Each node is pushed and popped from the stack at most once, resulting in a time complexity of O(n), where n is the size of the array.
• 🧺 Space complexity: O(n). The stack can hold up to n nodes in the worst case, making the space complexity O(n).

Dry Run

nums = [3,2,1,6,5,0]
3   stack:[3]            tree: 3
2   stack:[3, 2]         tree: 3
								\
								 2

1   stack:[3, 2, 1]      tree: 3
								\
								 2
								  \
								   1
6: a) 
	stack:[3, 2]         tree: 3 
								\
								 2   6
								  \ /
								   1
   stack:[3]             tree: 3   6
								\ /
								 2
								  \
								   1
  stack: []              tree: 6
							  /
							 3
							  \
							   2
								\
								 1
  stack 6                               

5: stack 6 5             tree: 6
							  / \
							 3   5
							  \
							   2
								\
								 1 

0: stack 6 5 0           tree:  6
							 /    \
							3      5
							 \    /
							  2  0
							   \
								1