Maximum Binary Tree

Patrick Leaton

Published: July 23, 2021, 8:09 p.m.

Problem Description

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

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

Return the maximum binary tree built from nums.

Example 1:

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:

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

Constraints:

1 <= nums.length <= 1000
0 <= nums[i] <= 1000
All integers in nums are unique.

The description was taken from https://leetcode.com/problems/maximum-binary-tree/.

Problem Solution

#O(N^2) Worst Time, O(Log N) Average, O(N) Space

class Solution:

def constructMaximumBinaryTree(self, nums: List[int]) -> TreeNode:

return self.construct_tree(nums, 0, len(nums))

def get_max(self, nums:list, left:int, right:int) -> int:

max_val, max_index = nums[left], left

for i in range(left, right):

if nums[i] > max_val:

max_val = nums[i]

max_index = i

return max_val, max_index

def construct_tree(self, nums:list, left:int, right:int) -> TreeNode:

if left == right:

return None

maximum = self.get_max(nums, left, right)

root, mid = TreeNode(maximum[0]), maximum[1]

root.left = self.construct_tree(nums, left, mid)

root.right = self.construct_tree(nums, mid+1, right)

return root

Problem Explanation

The solution to this problem is very similar to how we would build a binary tree from a sorted array, we would recursively get the middle node from the given range, split the remaining range in half, and recurse the function to build children from the two halves, excluding the node just created.

The only difference here is instead of recursively getting the local middle value to make a node from, we will be getting the local max.

Let's start by building the recursive function just mentioned.

The function will take the input array, a left pointer that begins the bounds of the current range, and a right pointer that ends it.

def construct_tree(self, nums:list, left:int, right:int) -> TreeNode:

Being a recursive function, let's make the base case first so that we don't get infinite function calls.

If the left pointer and right pointer have overlapped, then our bounds for building the node would be length zero. If that is the case, we will return from here.

if left == right:

return None

Otherwise, we will get the maximum value for the current range between left and right using a function we will build in a minute.

maximum = self.get_max(nums, left, right)

Once we get the value and the index of the local maximum, we will create a root node from it then set our left child as the return value for the maximum between the range of the left pointer up to the index directly before the mid pointer, and the right child as the return value for the maximum between the index directly after the mid pointer up to the right pointer.

root, mid = TreeNode(maximum[0]), maximum[1]

root.left = self.construct_tree(nums, left, mid)

root.right = self.construct_tree(nums, mid+1, right)

After we get our children's values for a given root, we will return the root so that we build the tree from the bottom-up.

return root

Let's build the get_max function.

It will also take a left pointer, a right pointer, and the input array.

def get_max(self, nums:list, left:int, right:int) -> int:

We will start off by initializing the maximum value and maximum index as the element at the left pointer and the left pointer itself. We are taking a guess that this is the maximum value, and if it isn't then these values will be overwritten within our traversal anyway.