All Elements in Two Binary Search Trees

MediumTreesbst

Solve this the way you would in the interview: out loud, on a timer, with an AI interviewer asking follow-ups while you code. You get a scored report at the end.

Practice this as a mock interviewFree to start, no account needed

Problem

You are given the roots of two binary search trees, root1 and root2. Return a list containing every value from both trees, sorted in non-decreasing order. Values within a single tree are distinct, but the same value may appear in both trees; in that case it appears twice in the output. Either tree may be empty. Sorting everything costs O(n log n). Aim for O(n + m) by using the order each BST already provides.

Examples

Input: root1 = [5,2,7], root2 = [4,1,6]
Output: [1,2,4,5,6,7]
The in-order sequences [2,5,7] and [1,4,6] merge into one sorted list.
Input: root1 = [3,null,9], root2 = [9,3]
Output: [3,3,9,9]
Both trees hold 3 and 9, so each value is listed twice.

Constraints

  • 0 <= number of nodes in each tree <= 5000
  • -10^5 <= Node.val <= 10^5
  • Values within one tree are distinct

What the interviewer grades

A correct solution is one of five scores. The report also grades problem understanding (did you clarify inputs and edge cases before coding), problem solving, communication while you work, code quality, and testing. See a sample report, or read up on the pattern in the lessons.

More bst problems