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

SimplyLeet
TagsCompaniesDisclaimersPrivacyTermsContactAbout Us

Maximum Binary Tree

Number: 654

Difficulty: Medium

Paid? No

Companies: Microsoft

Problem Description

Given an array of unique integers, construct a maximum binary tree by following these rules:

  1. The root is the maximum element in the array.
  2. The left subtree is built recursively from the subarray left of the maximum element.
  3. The right subtree is built recursively from the subarray right of the maximum element.

Key Insights

  • The maximum element in any subarray becomes the root of the (sub)tree.
  • The problem can be naturally solved using a recursive, divide and conquer approach.
  • Alternatively, a monotonic stack can be used to achieve an O(n) solution.
  • Handling base cases, such as an empty array, is crucial to prevent errors.

Space and Time Complexity

Time Complexity: O(n^2) in the worst-case (when the array is sorted in ascending or descending order) using the recursive approach; O(n) using a monotonic stack approach. Space Complexity: O(n) due to recursion stack or explicit stack usage.

Solution

We solve the problem recursively:

  • Identify the maximum element in the current array segment.
  • Create a tree node with this maximum value.
  • Recursively build the left subtree with the subarray left of the maximum element.
  • Recursively build the right subtree with the subarray right of the maximum element. This approach leverages the divide and conquer technique to build the tree in a structured manner.

Code Solutions

# Definition for a binary tree node.
class TreeNode:
    def __init__(self, val=0, left=None, right=None):
        self.val = val              # Node value
        self.left = left            # Left child
        self.right = right          # Right child

class Solution:
    def constructMaximumBinaryTree(self, nums: list[int]) -> TreeNode:
        # Base case: if nums is empty return None
        if not nums:
            return None
        # Find index of the maximum element in the list
        max_index = nums.index(max(nums))
        # Create a new TreeNode with the maximum element
        node = TreeNode(nums[max_index])
        # Recursively build the left subtree using elements before max_index
        node.left = self.constructMaximumBinaryTree(nums[:max_index])
        # Recursively build the right subtree using elements after max_index
        node.right = self.constructMaximumBinaryTree(nums[max_index + 1:])
        # Return the created tree node
        return node
← Back to All Questions