We use cookies (including Google cookies) to personalize ads and analyze traffic. By continuing to use our site, you accept our Privacy Policy.

SimplyLeet
TagsDisclaimersPrivacyTermsContactAbout Us

Maximum Binary Tree

Difficulty: Medium

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:

  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.

Key Insights

  • The maximum binary tree is constructed based on the maximum values of subarrays.
  • The left child is constructed from elements to the left of the maximum, and the right child from elements to the right.
  • The problem can be solved using a recursive divide-and-conquer approach.

Space and Time Complexity

Time Complexity: O(n) - Each element is processed once to find the maximum. Space Complexity: O(n) - The space required for the recursive stack and the tree nodes.

Solution

To solve the problem, we can use a recursive approach where we:

  1. Identify the maximum element in the current subarray.
  2. Create a new tree node for this maximum element.
  3. Recursively apply the same logic to the left subarray (elements before the maximum) and the right subarray (elements after the maximum).

This approach effectively builds the binary tree according to the specified rules.

Code Solutions

class TreeNode:
    def __init__(self, val=0, left=None, right=None):
        self.val = val
        self.left = left
        self.right = right

def constructMaximumBinaryTree(nums):
    if not nums:
        return None
    
    # Find the index of the maximum element
    max_index = nums.index(max(nums))
    
    # Create the root node with the maximum element
    root = TreeNode(nums[max_index])
    
    # Recursively construct the left and right subtrees
    root.left = constructMaximumBinaryTree(nums[:max_index])  # Left subarray
    root.right = constructMaximumBinaryTree(nums[max_index + 1:])  # Right subarray
    
    return root
← Back to All Questions