998. Maximum Binary Tree II

Time: O(n)

Space: O(n)

Intuition

Insert val at end of array. Walk right spine: if val > current node, new node becomes root with current node as left child.

Algorithm

1If root is null or val > root.val: return new TreeNode(val, root, null).
2root.right = insertIntoMaxTree(root.right, val). Return root.

Common Pitfalls

•Only the rightmost spine is affected by appending to end of array.

998.cs

// Approach: If val is larger than root insert as new root with old root as left child; otherwise recurse right to find insertion point.
// Time: O(n) Space: O(n)

public class TreeNode(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;
    }
}

Was this solution helpful?