FastPrepAll Elements of Two BSTs in Order

All Elements of Two BSTs in Order

Adobe logoAdobe● MediumFULLTIMEPHONE SCREEN

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 0 and 500 nodes.
  • -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 500 nodes.

More Adobe problems

All Adobe interview questionsSee Adobe hiring insights
Saved
public List<Integer> mergeBstValues(TreeNode root1, TreeNode root2) {
    // Write your code here.
}
Checking account…