We are given the root node of a maximum tree: a tree where every node has a value greater than any other value in its subtree.

Just as in the previous problem, the given tree was constructed from an 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 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]

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]

Note:

1. 1 <= B.length <= 100

Companies:
Facebook

Related Topics:
Tree

Similar Questions:

• Maximum Binary Tree (Medium)

• Find insertion point: Keep repeating the following logic until node becomes NULL
  • If val < node->val, go right.
  • Otherwise, break.
• Assume prev is the parent of node. The new node should be the right child of prev and node (which might be NULL) should be the left child of the new node.

// OJ: https://leetcode.com/problems/maximum-binary-tree-ii/
// Author: github.com/lzl124631x
// Time: O(N)
// Space: O(1)
class Solution {
public:
    TreeNode* insertIntoMaxTree(TreeNode* root, int val) {
        TreeNode *node = root, *prev = NULL;
        while (node && val < node->val) {
            prev = node;
            node = node->right;
        }
        auto n = new TreeNode(val);
        if (prev) prev->right = n;
        else root = n;
        n->left = node;
        return root;
    }
};