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

0% completed

Vote For New Content
Maximum Binary Tree (medium)
On this page

Problem Statement

Examples

Try it yourself

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!

On this page

Problem Statement

Examples

Try it yourself