1305. All Elements in Two Binary Search Trees


Problem Description

In this problem, we are given two binary search trees, root1 and root2. A binary search tree (BST) is a tree where each node has at most two children, known as the left child and the right child. In a BST, the left subtree of a node contains only nodes with keys less than the node's key, while the right subtree contains only nodes with keys greater than the node's key. Our task is to retrieve all the integers from both trees and return them as a list sorted in ascending order.

Intuition

Given that we're dealing with binary search trees, we can take advantage of their inherent properties to solve this problem efficiently:

  1. In-Order Traversal: A key insight is that performing an in-order traversal (Left, Node, Right) on a BST will visit the nodes in ascending order. Therefore, if we perform this traversal on both BSTs, we will get two sorted lists of values. In the given solution, the dfs function is a recursive function that conducts an in-order traversal and outputs the visited values into a list.

  2. Merging Sorted Lists: With two sorted lists from the BSTs, the next step is to merge these lists into one sorted list. This can be done efficiently by maintaining pointers at the front of each list and taking the smaller value from the front of either list at each step. The merge function in the given solution employs a two-pointer approach to combine the lists from the two BSTs into a single sorted list.

By breaking down the problem into two simpler subproblems—one focusing on tree traversal to obtain sorted elements and the other on merging sorted lists—we effectively construct a solution that leverages the characteristics of BSTs to achieve the desired result.

Solution Approach

The solution approach is divided into two main parts: performing in-order traversal on both trees to obtain sorted lists, and then merging these two sorted lists into one.

  1. In-Order Traversal: The first step involves writing a dfs (Depth-First Search) function to perform an in-order traversal of a binary search tree. The function takes a node (initially the root of a BST) and a list as arguments. If the current node is null, it returns immediately, as it signifies the end of a branch. Otherwise, it recursively calls itself for the left child, appends the node's value to the list, and then recursively calls itself for the right child. This approach ensures that each tree's values are added to their respective lists (t1 and t2) in ascending order. The traversal is defined by the following recursive algorithm:

    1def dfs(root, t):
    2    if root is None:
    3        return
    4    dfs(root.left, t)
    5    t.append(root.val)
    6    dfs(root.right, t)
  2. Merging Sorted Lists: After obtaining the sorted lists, the second part of the approach involves merging these two lists into one. The merge function introduces two pointers (i and j), starting at 0, pointing to the beginnings of t1 and t2 respectively. It compares the values at t1[i] and t2[j] and appends the lesser value to the ans list, incrementing the corresponding pointer (i++ or j++). If one list is exhausted before the other (one pointer reaches the end of its list), the remaining elements of the other list are appended to ans. This merging process yields a new sorted list resulting from combining t1 and t2. Here's the merging logic:

    1def merge(t1, t2):
    2    ans = []
    3    i = j = 0
    4    while i < len(t1) and j < len(t2):
    5        if t1[i] <= t2[j]:
    6            ans.append(t1[i])
    7            i += 1
    8        else:
    9            ans.append(t2[j])
    10            j += 1
    11    while i < len(t1):
    12        ans.append(t1[i])
    13        i += 1
    14    while j < len(t2):
    15        ans.append(t2[j])
    16        j += 1
    17    return ans

The algorithm comes together in the getAllElements method. It initializes two empty lists, t1 and t2, and then calls dfs on both root1 and root2, filling t1 and t2 with each tree's elements. Afterward, it calls merge on these lists to produce a single sorted list containing all the elements from both BSTs, which is finally returned.

By systematically dividing the problem into manageable subproblems, applying appropriate data structures (lists) and algorithms (DFS for tree traversal, merging for combining lists), the solution efficiently merges the elements from two BSTs into a sorted order.

💪
Level Up Your
Algo Skills

Example Walkthrough

Let's illustrate the solution approach using a small example. Consider the following two binary search trees:

1  Tree 1       Tree 2
2    3            2
3   / \          / \
4  1   4        1   7
  1. In-Order Traversal:

First, we perform an in-order traversal on Tree 1:

  • Visit left subtree: 1
  • Visit root: 3
  • Visit right subtree: 4

The sorted list t1 for Tree 1 is thus [1, 3, 4].

Next, we perform the same traversal on Tree 2:

  • Visit left subtree: 1
  • Visit root: 2
  • Visit right subtree: 7

The sorted list t2 for Tree 2 is [1, 2, 7].

  1. Merging Sorted Lists:

Now we have two sorted lists, t1 = [1, 3, 4] and t2 = [1, 2, 7]. We merge them into one list as follows:

  • Initialize ans = [], i = 0, j = 0
  • Compare t1[i] and t2[j]: 1 <= 1, append t1[i] to ans, increment i. Now ans = [1].
  • Compare new t1[i] and t2[j]: 3 > 1, append t2[j] to ans, increment j. Now ans = [1, 1].
  • Compare new t1[i] and t2[j]: 3 > 2, append t2[j] to ans, increment j. Now ans = [1, 1, 2].
  • Compare new t1[i] and t2[j]: 3 <= 7, append t1[i] to ans, increment i. Now ans = [1, 1, 2, 3].
  • Compare new t1[i] and t2[j]: 4 <= 7, append t1[i] to ans, increment i. Now ans = [1, 1, 2, 3, 4].
  • i has reached the end of t1, so we append the remaining elements of t2 ([7]) to ans. Now ans = [1, 1, 2, 3, 4, 7].

The merged sorted list ans is [1, 1, 2, 3, 4, 7], and that will be our final output. The solution approach leverages efficient in-order traversal to generate sorted lists from each tree, followed by a streamlined merge process, thus solving the problem effectively.

Python Solution

1# Definition for a binary tree node.
2class TreeNode:
3    def __init__(self, val=0, left=None, right=None):
4        self.val = val
5        self.left = left
6        self.right = right
7
8class Solution:
9    def getAllElements(self, root1: TreeNode, root2: TreeNode) -> List[int]:
10        # Helper function to perform in-order traversal of the binary tree
11        # and store the elements in a list.
12        def in_order_traversal(root: TreeNode, elements: List[int]):
13            if root is None:
14                return
15            in_order_traversal(root.left, elements)
16            elements.append(root.val)
17            in_order_traversal(root.right, elements)
18
19        # Helper function to merge two sorted lists into a single sorted list.
20        def merge_lists(sorted_list1: List[int], sorted_list2: List[int]) -> List[int]:
21            merged_list = []
22            i, j = 0, 0
23            # Interleave elements from both lists in a sorted manner.
24            while i < len(sorted_list1) and j < len(sorted_list2):
25                if sorted_list1[i] <= sorted_list2[j]:
26                    merged_list.append(sorted_list1[i])
27                    i += 1
28                else:
29                    merged_list.append(sorted_list2[j])
30                    j += 1
31            # Append any remaining elements from the first list
32            while i < len(sorted_list1):
33                merged_list.append(sorted_list1[i])
34                i += 1
35            # Append any remaining elements from the second list
36            while j < len(sorted_list2):
37                merged_list.append(sorted_list2[j])
38                j += 1
39            return merged_list
40
41        # Initialize lists to store the elements from each tree.
42        tree1_elements, tree2_elements = [], []
43        # Perform in-order traversal on both trees to get sorted elements.
44        in_order_traversal(root1, tree1_elements)
45        in_order_traversal(root2, tree2_elements)
46        # Merge the sorted lists and return the result.
47        return merge_lists(tree1_elements, tree2_elements)
48

Java Solution

1class Solution {
2    // This method returns a list of all elements from two binary tree roots.
3    public List<Integer> getAllElements(TreeNode root1, TreeNode root2) {
4        List<Integer> tree1Elements = new ArrayList<>();
5        List<Integer> tree2Elements = new ArrayList<>();
6        // Perform in-order traversal to get elements in non-descending order.
7        inorderTraversal(root1, tree1Elements);
8        inorderTraversal(root2, tree2Elements);
9        // Merge two sorted lists into one sorted list.
10        return mergeSortedLists(tree1Elements, tree2Elements);
11    }
12
13    // Helper method to perform a DFS in-order traversal.
14    private void inorderTraversal(TreeNode root, List<Integer> elements) {
15        if (root == null) {
16            return;
17        }
18        inorderTraversal(root.left, elements); // Visit left subtree
19        elements.add(root.val); // Visit current node
20        inorderTraversal(root.right, elements); // Visit right subtree
21    }
22
23    // Helper method to merge two sorted lists.
24    private List<Integer> mergeSortedLists(List<Integer> list1, List<Integer> list2) {
25        List<Integer> mergedList = new ArrayList<>();
26        int i = 0, j = 0;
27        // Merge elements while there are elements in both lists.
28        while (i < list1.size() && j < list2.size()) {
29            if (list1.get(i) <= list2.get(j)) {
30                mergedList.add(list1.get(i++)); // Add from list1 and increment i
31            } else {
32                mergedList.add(list2.get(j++)); // Add from list2 and increment j
33            }
34        }
35        // Add any remaining elements in list1 to the merged list.
36        while (i < list1.size()) {
37            mergedList.add(list1.get(i++));
38        }
39        // Add any remaining elements in list2 to the merged list.
40        while (j < list2.size()) {
41            mergedList.add(list2.get(j++));
42        }
43        return mergedList;
44    }
45}
46

C++ Solution

1#include <vector>
2
3// Definition for a binary tree node.
4struct TreeNode {
5    int val;
6    TreeNode *left;
7    TreeNode *right;
8    TreeNode() : val(0), left(nullptr), right(nullptr) {}
9    TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
10    TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}
11};
12
13class Solution {
14public:
15    // Retrieves all elements from both trees and returns them in a sorted vector.
16    vector<int> getAllElements(TreeNode* root1, TreeNode* root2) {
17        vector<int> elementsTree1;
18        vector<int> elementsTree2;
19      
20        // Traverse both trees and collect their values
21        depthFirstSearch(root1, elementsTree1);
22        depthFirstSearch(root2, elementsTree2);
23      
24        // Merge the collected values into a single sorted vector
25        return merge(elementsTree1, elementsTree2);
26    }
27
28    // Helper function to perform in-order depth-first search on the tree
29    // and collect values in a vector.
30    void depthFirstSearch(TreeNode* root, vector<int>& elements) {
31        if (!root) return;
32        depthFirstSearch(root->left, elements);  // Visit left subtree
33        elements.push_back(root->val);           // Visit node
34        depthFirstSearch(root->right, elements); // Visit right subtree
35    }
36
37    // Helper function to merge two sorted vectors into one sorted vector.
38    vector<int> merge(const vector<int>& tree1Elements, const vector<int>& tree2Elements) {
39        vector<int> mergedElements;
40        int i = 0, j = 0;
41
42        // Merge the two vectors until one is fully traversed.
43        while (i < tree1Elements.size() && j < tree2Elements.size()) {
44            if (tree1Elements[i] <= tree2Elements[j]) {
45                mergedElements.push_back(tree1Elements[i++]);
46            } else {
47                mergedElements.push_back(tree2Elements[j++]);
48            }
49        }
50
51        // Add the remaining elements from the first vector if any.
52        while (i < tree1Elements.size()) {
53            mergedElements.push_back(tree1Elements[i++]);
54        }
55
56        // Add the remaining elements from the second vector if any.
57        while (j < tree2Elements.size()) {
58            mergedElements.push_back(tree2Elements[j++]);
59        }
60
61        return mergedElements;
62    }
63};
64

Typescript Solution

1function getAllElements(root1: TreeNode | null, root2: TreeNode | null): number[] {
2    // Initialize the result array which will contain all the elements in sorted order.
3    const result: number[] = [];
4
5    // Use two stacks to perform inorder traversal on both trees simultaneously.
6    const stacks: [TreeNode[], TreeNode[]] = [[], []];
7
8    // Continue the traversal as long as there are nodes to be processed in either stack or trees.
9    while (root1 !== null || stacks[0].length > 0 || root2 !== null || stacks[1].length > 0) {
10        // Inorder traversal on the first tree.
11        while (root1 !== null) {
12            stacks[0].push(root1);
13            root1 = root1.left;  // Move to the left child.
14        }
15
16        // Inorder traversal on the second tree.
17        while (root2 !== null && (stacks[0].length === 0 || root2.val < stacks[0][stacks[0].length - 1].val)) {
18            stacks[1].push(root2);
19            root2 = root2.left;  // Move to the left child.
20        }
21
22        // Determine which tree's node value to take (the smaller one), and move to the right subtree.
23        if (stacks[0].length === 0 || 
24            (stacks[1].length > 0 && stacks[0][stacks[0].length - 1].val > stacks[1][stacks[1].length - 1].val)) {
25            const { val, right } = stacks[1].pop()!;
26            result.push(val);  // Add the value of the node to the result array.
27            root2 = right;     // Update root2 to the right child.
28        } else {
29            const { val, right } = stacks[0].pop()!;
30            result.push(val);  // Add the value of the node to the result array.
31            root1 = right;     // Update root1 to the right child.
32        }
33    }
34
35    // Return the result array containing all the elements from both trees in a sorted order.
36    return result;
37}
38

Time and Space Complexity

The above code consists of two major parts: the Depth-First Search (DFS) for in-order traversal and the Merge step to combine two sorted arrays. Let's analyze each part separately.

DFS In-order Traversal

The DFS function dfs() is called for each of the two binary trees. It traverses all nodes exactly once in a recursive in-order fashion (left, node, right).

  • Time Complexity for each tree: It's O(n) for root1 and O(m) for root2, where n and m represent the number of nodes in root1 and root2, respectively.
  • Space Complexity for each tree: Due to the recursion stack, the space complexity is O(h1) for root1 and O(h2) for root2, where h1 and h2 are the heights of the trees.

Merge Function

The merge() function merges two sorted arrays t1 and t2.

  • Time Complexity: As each element from both lists is considered exactly once, the time complexity of this operation is O(n + m).
  • Space Complexity: We're creating a new list ans to store the merged arrays, so the space complexity is O(n + m) as we are storing all n + m elements.

Overall Complexity

The total time complexity of getAllElements() is the sum of the complexities of both parts, dominated by the O(n + m) complexity of the merge step.

  • Time Complexity: O(n + m)
    • To be precise, it can be broken down to O(n) + O(m) + O(n + m), which simplifies to O(n + m).

The total space complexity is given by the space used to store the traversal results and the merge results, together with the recursion stack space.

  • Space Complexity: O(n + m) + max(O(h1), O(h2))
    • Here, O(n + m) is for the space needed for t1, t2, and ans, and max(O(h1), O(h2)) accounts for the recursive call stack space which will be at most the height of the taller tree at any instance.
😈
Become an
Algo Monster

Got a question? Ask the Teaching Assistant anything you don't understand.

Still not clear? Ask in the Forum,  Discord or Submit the part you don't understand to our editors.


TA 👨‍🏫