Grokking Data Structures & Algorithms for Coding Interviews
Ask Author
Back to course home

0% completed

Vote For New Content
Maximum Binary Tree (medium)
Table of Contents

Contents are not accessible

Contents are not accessible

Contents are not accessible

Contents are not accessible

Contents are not accessible

Problem Statement

Given an integer array nums with no duplicates, construct a maximum binary tree from a given array by following these rules:

  • The root of the tree is the highest value in the nums.
  • The left subtree is recursively built from the elements to the left of the highest value in subarray prefix.
  • The right subtree is recursively built from the elements to the right of the highest value in subarray suffix.

Return the resulting maximum binary tree.

Examples

Example 1:

  • Input: nums = [4, 3, 1, 7, 0, 5]
  • Expected Output: [7, 4, 5, null, 3, 0, null, null, 1]
Image
  • Justification:
    • The maximum value is 7, which becomes the root.
    • Left subarray [4, 3, 1] builds the left subtree:
      • Maximum is 4.
      • Right subarray [3, 1] builds further:
        • Maximum is 3 with right child 1.
    • Right subarray [0, 5] builds the right subtree:
      • Maximum is 5 with left child 0.

Example 2:

  • Input: nums = [1, 4, 3, 2]
  • Expected Output: [4, 1, 3, null, null, null, 2]
Image
  • Justification:
    • The maximum value is 4, which becomes the root.
    • Left subarray [1] becomes the left child.
    • Right subarray [3, 2] builds the right subtree:
      • Maximum is 3 with right child 2.

Example 3:

  • Input: nums = [7, 2, 5, 3, 9, 1]
  • Expected Output: [9, 7, 1, null, 5, null, null, 2, 3]
Image
  • Justification:
    • The maximum value is 9, which becomes the root.
    • Left subarray [7, 2, 5, 3] builds the left subtree:
      • Maximum is 7.
      • Right subarray [2, 5, 3] builds further:
        • Maximum is 5 with left child 2 and right child 3.
    • Right subarray [1] becomes the right child.

Constraints:

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

Try it yourself

Try solving this question here:

Python3
Python3
. . . .

.....

.....

.....

Like the course? Get enrolled and start learning!

Table of Contents

Contents are not accessible

Contents are not accessible

Contents are not accessible

Contents are not accessible

Contents are not accessible