In this guide, you will get 998. Maximum Binary Tree II LeetCode Solution with the best time and space complexity. The solution to Maximum Binary Tree II problem is provided in various programming languages like C++, Java, and Python. This will be helpful for you if you are preparing for placements, hackathons, interviews, or practice purposes. The solutions provided here are very easy to follow and include detailed explanations.
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]
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
Complexity Analysis
Time Complexity: O(n)
Space Complexity: O(h)
998. Maximum Binary Tree II LeetCode Solution in C++
class Solution {
public:
TreeNode* insertIntoMaxTree(TreeNode* root, int val) {
if (root == nullptr)
return new TreeNode(val);
if (root->val < val)
return new TreeNode(val, root, nullptr);
root->right = insertIntoMaxTree(root->right, val);
return root;
}
}; /* code provided by PROGIEZ */
998. Maximum Binary Tree II LeetCode Solution in Java
class Solution {
public TreeNode insertIntoMaxTree(TreeNode root, int val) {
if (root == null)
return new TreeNode(val);
if (root.val < val)
return new TreeNode(val, root, null);
root.right = insertIntoMaxTree(root.right, val);
return root;
}
} // code provided by PROGIEZ
998. Maximum Binary Tree II LeetCode Solution in Python
class Solution:
def insertIntoMaxTree(
self,
root: TreeNode | None,
val: int,
) -> TreeNode | None:
if not root:
return TreeNode(val)
if root.val < val:
return TreeNode(val, root, None)
root.right = self.insertIntoMaxTree(root.right, val)
return root # code by PROGIEZ
