1305. All Elements in Two Binary Search Trees - Leetcode Solution

Code Implementation

# Definition for a binary tree node.
# class TreeNode:
#     def __init__(self, val=0, left=None, right=None):
#         self.val = val
#         self.left = left
#         self.right = right

class Solution:
    def getAllElements(self, root1: TreeNode, root2: TreeNode) -> List[int]:
        def inorder(node):
            return inorder(node.left) + [node.val] + inorder(node.right) if node else []
        list1 = inorder(root1)
        list2 = inorder(root2)
        # Merge two sorted lists
        res = []
        i = j = 0
        while i < len(list1) and j < len(list2):
            if list1[i] < list2[j]:
                res.append(list1[i])
                i += 1
            else:
                res.append(list2[j])
                j += 1
        res.extend(list1[i:])
        res.extend(list2[j:])
        return res

// Definition for a binary tree node.
// struct TreeNode {
//     int val;
//     TreeNode *left;
//     TreeNode *right;
//     TreeNode() : val(0), left(nullptr), right(nullptr) {}
//     TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
//     TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}
// };

class Solution {
public:
    void inorder(TreeNode* node, vector<int>& out) {
        if (!node) return;
        inorder(node->left, out);
        out.push_back(node->val);
        inorder(node->right, out);
    }
    vector<int> getAllElements(TreeNode* root1, TreeNode* root2) {
        vector<int> v1, v2, res;
        inorder(root1, v1);
        inorder(root2, v2);
        int i = 0, j = 0;
        while (i < v1.size() && j < v2.size()) {
            if (v1[i] < v2[j]) res.push_back(v1[i++]);
            else res.push_back(v2[j++]);
        }
        while (i < v1.size()) res.push_back(v1[i++]);
        while (j < v2.size()) res.push_back(v2[j++]);
        return res;
    }
};

// Definition for a binary tree node.
// public class TreeNode {
//     int val;
//     TreeNode left;
//     TreeNode right;
//     TreeNode() {}
//     TreeNode(int val) { this.val = val; }
//     TreeNode(int val, TreeNode left, TreeNode right) {
//         this.val = val;
//         this.left = left;
//         this.right = right;
//     }
// }

import java.util.*;

class Solution {
    private void inorder(TreeNode node, List<Integer> out) {
        if (node == null) return;
        inorder(node.left, out);
        out.add(node.val);
        inorder(node.right, out);
    }
    public List<Integer> getAllElements(TreeNode root1, TreeNode root2) {
        List<Integer> l1 = new ArrayList<>();
        List<Integer> l2 = new ArrayList<>();
        inorder(root1, l1);
        inorder(root2, l2);
        List<Integer> res = new ArrayList<>();
        int i = 0, j = 0;
        while (i < l1.size() && j < l2.size()) {
            if (l1.get(i) < l2.get(j)) res.add(l1.get(i++));
            else res.add(l2.get(j++));
        }
        while (i < l1.size()) res.add(l1.get(i++));
        while (j < l2.size()) res.add(l2.get(j++));
        return res;
    }
}

/**
 * Definition for a binary tree node.
 * 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) {
    function inorder(node) {
        if (!node) return [];
        return [...inorder(node.left), node.val, ...inorder(node.right)];
    }
    let l1 = inorder(root1);
    let l2 = inorder(root2);
    let res = [];
    let i = 0, j = 0;
    while (i < l1.length && j < l2.length) {
        if (l1[i] < l2[j]) res.push(l1[i++]);
        else res.push(l2[j++]);
    }
    while (i < l1.length) res.push(l1[i++]);
    while (j < l2.length) res.push(l2[j++]);
    return res;
};

Problem Description

Given two binary search trees, root1 and root2, return a list containing all the elements from both trees in ascending order.

Each tree node contains an integer value.
Both trees are binary search trees (BSTs), meaning for any node, left subtree values are less, right subtree values are greater.
You must return a single sorted list containing all the elements from both trees.
Each element from both trees should appear in the result exactly as many times as it appears in the trees (do not reuse or omit elements).
The result should be in ascending order.
There is one valid solution for each input.

Thought Process

At first glance, the problem seems to require combining two sets of numbers and sorting them. The brute-force way would be to traverse each tree, collect all values into a list, and simply sort the resulting list. However, since both trees are BSTs, we know that an in-order traversal of each tree will produce a sorted list of its elements. This property suggests an optimization: rather than sorting after collecting, we can merge the two sorted lists using the same logic as the merge step in merge sort, which is more efficient.

The main conceptual shift is realizing that we can exploit the BST property to get sorted lists for free, and then efficiently merge them, instead of doing unnecessary sorting work after combining.

Solution Approach

Step 1: In-order Traversal
Perform an in-order traversal on each tree. In-order traversal visits nodes in "left, root, right" order, which for BSTs yields sorted values. We collect the results from both trees into two separate lists.
Step 2: Merge Sorted Lists
Now we have two sorted lists. We merge them into a single sorted list using a two-pointer technique:
- Start two pointers at the beginning of each list.
- Compare the pointed values and append the smaller one to the result, moving that pointer forward.
- Continue until both lists are exhausted, appending any remaining elements at the end.
Step 3: Return the Result
The merged list now contains all elements from both BSTs, in ascending order, as required.

This approach is efficient because both the in-order traversal and the merge step are linear in the number of nodes.

Example Walkthrough

Suppose we have the following trees:

Tree 1:

        2
       / \
      1   4

Tree 2:

        1
         \
          3

Step 1: In-order Traversal

Tree 1 in-order: [1, 2, 4]
Tree 2 in-order: [1, 3]

Step 2: Merge

Compare 1 and 1 → append 1 (from Tree 1), move pointer in Tree 1
Compare 2 and 1 → append 1 (from Tree 2), move pointer in Tree 2
Compare 2 and 3 → append 2, move pointer in Tree 1
Compare 4 and 3 → append 3, move pointer in Tree 2
Tree 2 exhausted, append remaining 4

Result: [1, 1, 2, 3, 4]

Time and Space Complexity

Brute-force Approach:
- Traverse both trees: O(m + n)
- Sort combined list: O((m + n) log(m + n))
- Total: O((m + n) log(m + n)) time, O(m + n) space
Optimized Approach (current solution):
- In-order traversal of both trees: O(m + n)
- Merge two sorted lists: O(m + n)
- Total: O(m + n) time, O(m + n) space (for storing result and traversed lists)
Why: Each node is visited exactly once in traversal, and the merge step compares each element once.

Summary

By leveraging the in-order traversal property of binary search trees, we efficiently obtain two sorted lists of elements. Merging these lists with a two-pointer technique yields a sorted result in linear time. This approach avoids unnecessary sorting and utilizes the structure of BSTs for an elegant, optimal solution.

AlgoMap.io

Want Help Cracking FAANG?