#1305

Medium

auto_awesomeBinary-tree traversal and state tracking

LeetCode Problem Workspace

All Elements in Two Binary Search Trees

Merge elements from two binary search trees and return them sorted in ascending order.

tree depth first search binary search tree sorting binary tree

Problem Statement

You are given two binary search trees, root1 and root2. Your task is to return a list that contains all the integers from both trees, sorted in ascending order. Each binary search tree is structured such that the left child is smaller than the parent node and the right child is larger. You need to find an efficient way to combine both trees into a single sorted list.

To solve this, consider using a tree traversal method such as DFS (Depth-First Search) or an iterative method to extract elements from both trees. Ensure the final output is sorted without needing to explicitly sort a large list, as the trees themselves maintain a sorted structure.

Examples

Example 1

Input: root1 = [2,1,4], root2 = [1,0,3]

Output: [0,1,1,2,3,4]

Example details omitted.

Example 2

Input: root1 = [1,null,8], root2 = [8,1]

Output: [1,1,8,8]

Example details omitted.

Constraints

The number of nodes in each tree is in the range [0, 5000].
-105 <= Node.val <= 105

Solution Approach

In-Order Traversal

The first approach is to use an in-order traversal to extract elements from both trees. Since in-order traversal visits nodes in sorted order in a BST, you can traverse both trees and merge the results on the fly. This avoids the need to sort the list at the end, making the solution more efficient.

Using Two-Pointer Technique

A two-pointer technique can be applied after obtaining the in-order traversal of both trees. Once you have two sorted lists, you can merge them in linear time, taking advantage of the fact that both lists are already ordered.

Depth-First Search (DFS)

Another approach is to perform a DFS on both trees, simulating the process of 'flattening' both trees into sorted lists while tracking the state of traversal. This can be done recursively or iteratively, depending on preference, and the merging happens as elements are processed.

Complexity Analysis

Metric	Value
Time	Depends on the final approach
Space	Depends on the final approach

The time complexity depends on the approach used. If performing in-order traversal and merging the lists, the time complexity is O(N + M), where N and M are the sizes of the two trees. Space complexity can vary, but it typically involves storing the result list and some auxiliary space for recursion (O(H) for DFS, where H is the height of the tree).

What Interviewers Usually Probe

Can the candidate efficiently merge two sorted lists using a two-pointer technique?
Does the candidate understand the trade-offs between DFS and iterative approaches?
How well does the candidate handle recursion or stack-based tree traversal methods?

Common Pitfalls or Variants

Common pitfalls

Not using in-order traversal, which results in an unnecessary sort step at the end.
Ignoring the fact that both trees are already sorted, leading to inefficient solutions.
Overcomplicating the solution by not merging the two trees while traversing.

Follow-up variants

What if one of the trees is empty?
How would the solution change if the trees were not binary search trees?
Can the problem be solved without using extra space?

FAQ

What is the optimal approach for merging two BSTs?

The optimal approach involves performing in-order traversal on both trees and merging them using the two-pointer technique.

How do I ensure the merged result is sorted?

In-order traversal ensures that elements from both trees are extracted in sorted order. Merging two sorted lists further maintains this order.

What if one of the trees is empty?

If one of the trees is empty, simply return the in-order traversal of the non-empty tree.

Can I solve this problem without recursion?

Yes, iterative solutions using a stack or a queue can replace recursion for DFS-based tree traversal.

How does this problem relate to binary-tree traversal?

This problem relies heavily on tree traversal techniques like in-order traversal to efficiently extract and merge elements from two binary search trees.

terminal

Solution

Solution 1: DFS + Merge

Since both trees are binary search trees, we can obtain the node value sequences $\textit{a}$ and $\textit{b}$ of the two trees through in-order traversal. Then, we use two pointers to merge the two sorted arrays to get the final answer.

1

2

3

4

5

6

7

8

9

10

11

12

13

14

15

16

17

18

19

20

21

22

23

24

25

26

27

28

29

30

31

32

33

34

35

36

37

# 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: Optional[TreeNode], root2: Optional[TreeNode]
    ) -> List[int]:
        def dfs(root: Optional[TreeNode], nums: List[int]) -> int:
            if root is None:
                return
            dfs(root.left, nums)
            nums.append(root.val)
            dfs(root.right, nums)

        a, b = [], []
        dfs(root1, a)
        dfs(root2, b)
        m, n = len(a), len(b)
        i = j = 0
        ans = []
        while i < m and j < n:
            if a[i] <= b[j]:
                ans.append(a[i])
                i += 1
            else:
                ans.append(b[j])
                j += 1
        while i < m:
            ans.append(a[i])
            i += 1
        while j < n:
            ans.append(b[j])
            j += 1
        return ans

Continue Practicing

#1373 maximum sum bst in binary tree #1382 balance a binary search tree #1038 binary search tree to greater sum tree