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