Maximum Binary Tree
Given an integer array nums
with no duplicates, the task is to construct a maximum binary tree using a specific algorithm. The root node’s value should be the maximum value in nums
, and the left and right subtrees are constructed recursively from the subarray prefix to the left and right of the maximum value, respectively.
Algorithm
Base Case: If the array or subarray is empty, return
None
.Find the Maximum: Find the index of the maximum value in the current array or subarray.
Create Root Node: Create a node with the maximum value.
Recursively Build Left and Right Subtrees:
 Left Subtree: Call the function recursively with the subarray to the left of the maximum value.
 Right Subtree: Call the function recursively with the subarray to the right of the maximum value.
Connect Root with Subtrees: Connect the left and right subtrees to the root node.
Return Root: Return the root node of the constructed tree.
Code


Explanation
 The algorithm begins by checking if the current array is empty. If it is, it returns
None
.  It then finds the maximum value and its index in the array.
 Using the index of the maximum value, the algorithm constructs the left and right subtrees by recursively calling itself with the appropriate subarrays.
 Finally, it connects the subtrees to the root node and returns the root.
Insights
 Time Complexity: ( O(n^2) ) in the worst case, where ( n ) is the length of the array. This complexity arises when the tree is skewed, and the array is searched for the maximum value at each recursive call.
 Space Complexity: ( O(n) ), mainly due to the recursion stack.
The given code efficiently constructs a maximum binary tree from an integer array following the provided algorithm, building the tree from the top down by selecting the maximum values for each node.
Define the Interface Input: Array of integers Output: TreeNode instance (root)
Define the Terms Maximum Binary Tree The root will hold the maximum number in the array. The left subtree is the maximum tree constructed from left side of the subarray divided by the maximum number. The right subtree is the maximum tree constructed from right side of subarray divided by the maximum number. Not a BST Is it the same as heap?
Subarray Prefix Everything to the left of the root is subarray prefix.
Subarray Suffix Everything on the right of the root is subarray suffix.
Constraints
 array length is in the range [1, 1000] inclusive
 values of the nodes are in the range [0, 1000] inclusive
Assumptions
 The numbers are unique
 There are no duplicates
How to construct the Maximum Binary Tree
 Find max
 Create the left subtree using the subarray prefix
 Create the right subtree using the subarray suffix
Two subproblems: left subtree, right subtree
Recursive Approach
Base Case What is the smallest instance of the problem? How do you climb tree? How do you unwind from the recursive calls? Keep track of visited node in a set, if the number of elements in the set is equal to the length of the array, then we can stop the recursion.
Keep finding the max from nums, when you run out of elements from nums we stop recursive calls. We pay the penalty in terms of performance.
So we need use indices to keep track of the subarray prefix and subarray suffix.
We need a helper function so that we can add start index and end index that will be used to create a subtree.
This is similar to Binary Search
 We are running two binary search
Do we need to check start == end or start > end to terminate the recursion?
i j
[3,2,1,6,0,5] i. m1 m+1 j [3,2,1, 6, 0, 5] i m1 [3,2, 1, 6, 0,
 We are running two binary search
Do we need to check start == end or start > end to terminate the recursion?
i j
How do we go down the tree from root to leaf? 
Unit of Work What is the smallest slice of work that needs to be done in each recursive call? Do we need to have a method to find the max value? Yes. Should we return the index at which the max value exists or return the actual value?
 Return the index. => We will be performing the unit of work before the recursive call.
 We need to create one root node object
 We need to create intermediate node objects
 We need to create leaves
Create the TreeNode before the recursive calls.
Can we treat them all the same?
Return the reference to 6 (root node)
Time: O( ) Space: O( )
Key Takeaways

