All Elements in Two Binary Search Trees

Medium
1944.

All Elements in Two Binary Search Trees

All Elements in Two Binary Search Trees is a medium coding problem on sorting, depth-first search and trees, asked in Amazon, Microsoft and Meta interviews.

You are given the roots root1 and root2 of two binary search trees (in each, every value in a node's left subtree is smaller than the node's value and every value in its right subtree is larger).

Return one list holding every value from both trees, sorted in ascending order. A value present in both trees appears twice.

Example 1

Input
root1 = [2,1,4], root2 = [1,0,3]
Output
[0,1,1,2,3,4]
Explanation
The first tree holds 1, 2, 4 and the second 0, 1, 3; together, sorted: 0, 1, 1, 2, 3, 4.

Example 2

Input
root1 = [1,null,8], root2 = [8,1]
Output
[1,1,8,8]
Explanation
Values that appear in both trees appear twice in the answer.

Example 3

Input
root1 = [], root2 = [5,1,7]
Output
[1,5,7]
Explanation
The first tree is empty, so the answer is just the second tree in order.

Constraints

  • 0 <= number of nodes in each tree <= 5000
  • -10^5 <= Node.val <= 10^5
  • each tree is a valid binary search tree
Write your solution here. Running it against the tests needs a free account — what you type comes with you.Sign in to run
/**
 * Definition for a binary tree node (provided by the judge — do not redefine it):
 * function TreeNode(val, left, right) {
 *     this.val = (val===undefined ? 0 : val)
 *     this.left = (left===undefined ? null : left)
 *     this.right = (right===undefined ? null : right)
 * }
 */
/**
 * @param {TreeNode} root1
 * @param {TreeNode} root2
 * @return {number[]}
 */
var getAllElements = function(root1, root2) {
    // Write your code here
    
};

Sign in to run your own test cases

Sign in

All Elements in Two Binary Search Trees — Problem & Solution

All Elements in Two Binary Search Trees solution explained: step-by-step approach, complexity and code in Python, Java, C++ and JavaScript. A medium problem.

All Elements in Two Binary Search Trees is a medium coding problem on sorting, depth-first search and trees, asked in Amazon, Microsoft and Meta interviews.

Problem statement

You are given the roots root1 and root2 of two binary search trees (in each, every value in a node's left subtree is smaller than the node's value and every value in its right subtree is larger).

Return one list holding every value from both trees, sorted in ascending order. A value present in both trees appears twice.

Example 1

Input: root1 = [2,1,4], root2 = [1,0,3]
Output: [0,1,1,2,3,4]
Explanation: The first tree holds 1, 2, 4 and the second 0, 1, 3; together, sorted: 0, 1, 1, 2, 3, 4.

Example 2

Input: root1 = [1,null,8], root2 = [8,1]
Output: [1,1,8,8]
Explanation: Values that appear in both trees appear twice in the answer.

Example 3

Input: root1 = [], root2 = [5,1,7]
Output: [1,5,7]
Explanation: The first tree is empty, so the answer is just the second tree in order.

Constraints

  • 0 <= number of nodes in each tree <= 5000
  • -10^5 <= Node.val <= 10^5
  • each tree is a valid binary search tree

Hints for All Elements in Two Binary Search Trees

  1. Hint 1

    An in-order walk of a binary search tree lists its values already sorted.

  2. Hint 2

    So you have two sorted lists — you do not need a general sort.

  3. Hint 3

    Merge them the way merge sort does: repeatedly take the smaller front element, then append whatever is left.

How to solve All Elements in Two Binary Search Trees

In-order traversal turns each BST into a sorted list in linear time, and two sorted lists merge into one in linear time.

Approach

  1. Walk each tree in order (left, node, right), appending values to its own list.
  2. Keep an index into each list; while both have elements left, append the smaller front value and advance that index.
  3. Append the rest of whichever list is not exhausted.

Why it works

The BST property makes every value of the left subtree smaller than the node and every value of the right subtree larger, so in-order output is sorted. The merge always appends the smallest value not yet used, so its output is sorted and contains every value exactly once per occurrence.

Complexity

  • Time — O(n + m)
  • Space — O(n + m) for the lists, plus O(h) recursion

Pitfalls

  • Concatenating and sorting works but costs O((n + m) log(n + m)); the merge is linear.
  • Either tree may be empty.

Reference solution

Python

from typing import List, Optional

def getAllElements(root1: Optional[TreeNode], root2: Optional[TreeNode]) -> List[int]:
    def inorder(node, out):
        if node is None:
            return
        inorder(node.left, out)
        out.append(node.val)
        inorder(node.right, out)

    a, b = [], []
    inorder(root1, a)
    inorder(root2, b)
    out = []
    i = j = 0
    while i < len(a) and j < len(b):
        if a[i] <= b[j]:
            out.append(a[i])
            i += 1
        else:
            out.append(b[j])
            j += 1
    out.extend(a[i:])
    out.extend(b[j:])
    return out

Java

public static int[] getAllElements(TreeNode root1, TreeNode root2) {
    List<Integer> a = new ArrayList<>(), b = new ArrayList<>();
    inorderInto(root1, a);
    inorderInto(root2, b);
    int[] out = new int[a.size() + b.size()];
    int i = 0, j = 0, k = 0;
    while (i < a.size() && j < b.size()) out[k++] = a.get(i) <= b.get(j) ? a.get(i++) : b.get(j++);
    while (i < a.size()) out[k++] = a.get(i++);
    while (j < b.size()) out[k++] = b.get(j++);
    return out;
}

static void inorderInto(TreeNode node, List<Integer> out) {
    if (node == null) return;
    inorderInto(node.left, out);
    out.add(node.val);
    inorderInto(node.right, out);
}

C++

void inorderInto(TreeNode* node, vector<int>& out);

vector<int> getAllElements(TreeNode* root1, TreeNode* root2) {
    vector<int> a, b, out;
    inorderInto(root1, a);
    inorderInto(root2, b);
    size_t i = 0, j = 0;
    while (i < a.size() && j < b.size()) out.push_back(a[i] <= b[j] ? a[i++] : b[j++]);
    while (i < a.size()) out.push_back(a[i++]);
    while (j < b.size()) out.push_back(b[j++]);
    return out;
}

void inorderInto(TreeNode* node, vector<int>& out) {
    if (!node) return;
    inorderInto(node->left, out);
    out.push_back(node->val);
    inorderInto(node->right, out);
}

JavaScript

var getAllElements = function(root1, root2) {
    var a = [], b = [], out = [];
    inorderInto(root1, a);
    inorderInto(root2, b);
    var i = 0, j = 0;
    while (i < a.length && j < b.length) out.push(a[i] <= b[j] ? a[i++] : b[j++]);
    while (i < a.length) out.push(a[i++]);
    while (j < b.length) out.push(b[j++]);
    return out;
};

var inorderInto = function(node, out) {
    if (node === null) return;
    inorderInto(node.left, out);
    out.push(node.val);
    inorderInto(node.right, out);
};

Also on the editorial tab: C, C#, Go, Kotlin, PHP, Ruby, Rust, Swift, TypeScript.

All 274 sorting problems · the whole catalogue

Learn the technique: Sorting Algorithms · Depth-First Search (DFS)