Skip to content

998. Maximum Binary Tree II 👎

Approach 1: Recursive

  • Time: $O(n)$
  • Space: $O(h)$
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
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;
  }
};

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
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;
  }
}

1
2
3
4
5
6
7
8
class Solution:
  def insertIntoMaxTree(self, root: Optional[TreeNode], val: int) -> Optional[TreeNode]:
    if not root:
      return TreeNode(val)
    if root.val < val:
      return TreeNode(val, root, None)
    root.right = self.insertIntoMaxTree(root.right, val)
    return root

Approach 2: Iterative

  • Time: $O(n)$
  • Space: $O(1)$
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
class Solution {
 public:
  TreeNode* insertIntoMaxTree(TreeNode* root, int val) {
    if (root->val < val)
      return new TreeNode(val, root, nullptr);
    TreeNode* curr = root;
    while (curr->right && curr->right->val > val)
      curr = curr->right;
    TreeNode* inserted = new TreeNode(val, curr->right, nullptr);
    curr->right = inserted;
    return root;
  }
};

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
class Solution {
  public TreeNode insertIntoMaxTree(TreeNode root, int val) {
    if (root.val < val)
      return new TreeNode(val, root, null);
    TreeNode curr = root;
    while (curr.right != null && curr.right.val > val)
      curr = curr.right;
    TreeNode inserted = new TreeNode(val, curr.right, null);
    curr.right = inserted;
    return root;
  }
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
class Solution:
  def insertIntoMaxTree(self, root: Optional[TreeNode], val: int) -> Optional[TreeNode]:
    if root.val < val:
      return TreeNode(val, root, None)
    curr = root
    while curr.right and curr.right.val > val:
      curr = curr.right
    inserted = TreeNode(val, curr.right, None)
    curr.right = inserted
    return root