Append to a Peak Tree

Medium

A peak tree is built from an array of distinct numbers like this: the root is the largest number in the array, the left subtree is built recursively from the part to its left, and the right subtree from the part to its right; an empty part gives an empty subtree. You are given the root of such a tree (the array itself is not given) and a number value that does not occur in the tree. The array has been extended by appending value to its end. Return the root of the peak tree built from the new array.

Example 1

root=tree_node([9, 4, 6, None, 2]), value=5 → [9, 4, 6, None, 2, None, 5]

The tree was built from [4, 2, 9, 6]. Appending gives [4, 2, 9, 6, 5]: the root is still 9, and 5 appears as the right child of 6.

Example 2

root=tree_node([9, 4, 6, None, 2]), value=12 → [12, 9, None, 4, 6, None, 2]

12 is larger than everything, so it becomes the new root and the whole old tree becomes its left subtree: every earlier number lies to the left of 12 in the array.

Example 3

root=tree_node([8, None, 3]), value=5 → [8, None, 5, 3]

The array was [8, 3] and becomes [8, 3, 5]. To the right of 8 is now [3, 5] rooted at 5, and 3 moves under it as the left child.

Constraints

1 ≤ number of nodes ≤ 100
1 ≤ Node.val ≤ 100, all values are distinct
root is a valid peak tree
1 ≤ value ≤ 100, and value does not occur in the tree

Have you seen this problem in a real interview?

Solved by0

Tried by0

Submissions0

Acceptance—

Topics

Tree Binary Tree