Scale Engineer

Maximum Binary Tree II

Med
#0952Time: O(N^2), where N is the number of nodes in the original tree. The in-order traversal takes O(N). The construction of the new tree from an array of size N+1 takes O((N+1)^2) because for each node, we scan a subarray to find the maximum.Space: O(N). We need O(N) space to store the array `a` (and `b`). The recursion stack for both traversal and construction can go up to O(N) in the case of a skewed tree.
Data structures
TreeBinary Tree

Prompt

A maximum tree is a tree where every node has a value greater than any other value in its subtree.

You are given the root of a maximum binary tree and an integer val.

Just as in the previous problem, the given tree was constructed from a list a (root = Construct(a)) recursively with the following Construct(a) routine:

  • If a is empty, return null.
  • Otherwise, let a[i] be the largest element of a. Create a root node with the value a[i].
  • The left child of root will be Construct([a[0], a[1], ..., a[i - 1]]).
  • The right child of root will be Construct([a[i + 1], a[i + 2], ..., a[a.length - 1]]).
  • Return root.

Note that we were not given a directly, only a root node root = Construct(a).

Suppose b is a copy of a with the value val appended to it. It is guaranteed that b has unique values.

Return Construct(b).

 

Example 1:

Input: root = [4,1,3,null,null,2], val = 5
Output: [5,4,null,1,3,null,null,2]
Explanation: a = [1,4,2,3], b = [1,4,2,3,5]

Example 2:

Input: root = [5,2,4,null,1], val = 3
Output: [5,2,4,null,1,null,3]
Explanation: a = [2,1,5,4], b = [2,1,5,4,3]

Example 3:

Input: root = [5,2,3,null,1], val = 4
Output: [5,2,4,null,1,3]
Explanation: a = [2,1,5,3], b = [2,1,5,3,4]

 

Constraints:

  • The number of nodes in the tree is in the range [1, 100].
  • 1 <= Node.val <= 100
  • All the values of the tree are unique.
  • 1 <= val <= 100

Approaches

3 approaches with complexity analysis and trade-offs.

This approach follows a straightforward, brute-force method. First, it reconstructs the original array a from which the given maximum binary tree was built. Then, it appends the new value val to this array to form a new array b. Finally, it constructs a new maximum binary tree from the array b using the standard construction algorithm.

Algorithm

  • Create an empty list, say a.
  • Perform an in-order traversal on the input tree root. During the traversal, add each visited node's value to the list a.
  • Append the given val to the list a.
  • Construct a new maximum binary tree from the modified list a using the recursive construction algorithm.
  • Return the root of the newly constructed tree.

Walkthrough

The core idea is to reverse the construction process to get the original data, modify the data, and then re-apply the construction process.

Step 1: Reconstruct the original array a. A key property of the maximum binary tree is that an in-order traversal of the tree yields the original array a. We perform an in-order traversal on the given root and store the node values in a list.

Step 2: Append val to form b. After obtaining the list a, we simply append the new integer val to it to get the list b.

Step 3: Construct the new tree from b. We implement the Construct(b) routine as described in the problem. This function recursively finds the maximum element in the current segment of the array, creates a root with it, and then builds the left and right subtrees from the parts of the array to the left and right of the maximum element.

class Solution {    public TreeNode insertIntoMaxTree(TreeNode root, int val) {        List<Integer> a = new ArrayList<>();        inorder(root, a);        a.add(val);        return construct(a, 0, a.size() - 1);    }     private void inorder(TreeNode node, List<Integer> list) {        if (node == null) {            return;        }        inorder(node.left, list);        list.add(node.val);        inorder(node.right, list);    }     private TreeNode construct(List<Integer> nums, int left, int right) {        if (left > right) {            return null;        }        int maxIndex = -1;        int maxVal = -1;        for (int i = left; i <= right; i++) {            if (nums.get(i) > maxVal) {                maxVal = nums.get(i);                maxIndex = i;            }        }        TreeNode node = new TreeNode(maxVal);        node.left = construct(nums, left, maxIndex - 1);        node.right = construct(nums, maxIndex + 1, right);        return node;    }}

Complexity

Time

O(N^2), where N is the number of nodes in the original tree. The in-order traversal takes O(N). The construction of the new tree from an array of size N+1 takes O((N+1)^2) because for each node, we scan a subarray to find the maximum.

Space

O(N). We need O(N) space to store the array `a` (and `b`). The recursion stack for both traversal and construction can go up to O(N) in the case of a skewed tree.

Trade-offs

Pros

  • Conceptually simple and easy to understand.

  • Directly simulates the problem definition.

Cons

  • Highly inefficient. It rebuilds the entire tree from scratch, even though the change is localized.

  • Requires significant extra space to store the intermediate array.

Solutions

/** * Definition for a binary tree node. * public class TreeNode { * int val; * TreeNode left; * TreeNode right; * TreeNode() {} * TreeNode(int val) { this.val = val; } * TreeNode(int val, TreeNode left, TreeNode right) { * this.val = val; * this.left = left; * this.right = right; * } * } */ class Solution { public TreeNode insertIntoMaxTree ( TreeNode root , int val ) { if ( root == null || root . val < val ) { return new TreeNode ( val , root , null ); } root . right = insertIntoMaxTree ( root . right , val ); return root ; } }

Video walkthrough

Newsletter

One sharp idea, every week

System design and interview prep — short enough to finish.

No spam. Unsubscribe anytime.

Practice

Same difficulty — related problems to reinforce the pattern.

← Previous

Previous problem

Next →

Next problem