All Elements of Two BSTs in Order
Problem statement
You are given the roots of two binary search trees, root1 and root2. Return one list that holds every value from both trees, sorted from smallest to largest.
In each tree, every node's value is larger than all values in its left subtree and smaller than all values in its right subtree.
- Either tree, or both, can be empty.
- A value can appear in both trees. Then it appears twice in the answer, once for each tree.
Function
mergeBstValues(root1: TreeNode, root2: TreeNode) → List<Integer>Examples
Example 1
root1 = [6,2,9]root2 = [5,2,8]return = [2,2,5,6,8,9]The first tree holds 2, 6, 9 and the second holds 2, 5, 8. Put together in order, they give 2, 2, 5, 6, 8, 9. The value 2 is in both trees, so it appears twice.
Example 2
root1 = []root2 = [5,1,7]return = [1,5,7]The first tree is empty. The answer is just the second tree's values in order: 1, 5, 7.
Example 3
root1 = [10,null,20,null,30]root2 = [25]return = [10,20,25,30]The first tree is a chain that only goes right: 10, then 20, then 30. The second tree is the single value 25, which fits between 20 and 30.
Constraints
- Each tree has between
0and500nodes. -10^4 <= node.val <= 10^4- Each tree follows the binary search tree rule, so the values inside one tree are all different.
- A tree does not have to be balanced. It can be a single chain of
500nodes.