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:
a is empty, return null.a[i] be the largest element of a. Create a root node with the value a[i].root will be Construct([a[0], a[1], ..., a[i - 1]]).root will be Construct([a[i + 1], a[i + 2], ..., a[a.length - 1]]).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:
[1, 100].1 <= Node.val <= 1001 <= val <= 100This approach involves recursively inserting the new value into the correct position in the maximum binary tree. The main idea is to find the correct place in the tree for the new value by comparing it with the current node values as we traverse the tree from top to bottom.
If the new value is greater than the root node, the new value becomes the new root, and the entire existing tree becomes its left subtree. Otherwise, recursively consider this insertion as a problem for the root's right subtree, as all existing left-side nodes are already smaller than the current root.
We define a TreeNode class to represent each node in the tree. The insertIntoMaxTree function accepts the root of the tree and an integer val. If the root is null (empty tree) or the val is greater than the root's value, we make val the new root node with the current root as its left child. Otherwise, we recursively try to insert val into the right subtree.
C++
Time Complexity: O(n), where n is the number of nodes in the tree.
Space Complexity: O(n) in the worst case due to the recursion stack.
This approach attempts to solve the problem using an iterative method with the help of a stack to simulate the recursive behavior. As the new value is only appended to the right-most part of the implied array, we have to check from right to left in the tree structure to find the appropriate place for the new value to maintain the maximum tree property.
The main idea is to traverse the right nodes of the tree using a stack until we find the correct position for the new node.
This solution uses a loop instead of a recursive approach to insert the node. We iterate down the chain of right children until we find a spot where the new node should be inserted. This will involve attaching the new node's left subtree as the right child of the current node.
JavaScript
Time Complexity: O(n), where n is the number of nodes in the tree.
Space Complexity: O(1) since additional structures (e.g., a stack) are not used.
| Approach | Complexity |
|---|---|
| Recursive Tree Modification | Time Complexity: O(n), where |
| Iterative Approach using Stack | Time Complexity: O(n), where |
Binary Tree Maximum Path Sum - DFS - Leetcode 124 - Python • NeetCode • 187,670 views views
Watch 9 more video solutions →Practice Maximum Binary Tree II with our built-in code editor and test cases.
Practice on FleetCode