How do you solve All Elements in Two Binary Search Trees on LeetCode?

All Elements in Two Binary Search Trees (LeetCode #1305) can be solved using Brute Force or Optimal Solution. The optimal approach is Optimal Solution with O(n) time complexity and O(n) space complexity. Key insight: In-order traversal of BSTs gives sorted elements.

What is the brute force solution for All Elements in Two Binary Search Trees?

The brute force approach for All Elements in Two Binary Search Trees is Brute Force, with O(n²) time complexity and O(n) space complexity. The brute force approach involves traversing both binary search trees (BSTs) to collect all their elements into a list, then sorting that list. This is straightforward but inefficient due to the sorting step. The optimal Optimal Solution approach improves this to O(n).

What are the interview tips for All Elements in Two Binary Search Trees?

Explain your thought process clearly. Consider edge cases and test your solution. Practice merging sorted arrays as it's a common pattern.

What are common mistakes when solving All Elements in Two Binary Search Trees?

Not using in-order traversal to collect elements. Forgetting to handle edge cases like empty trees.

#1305

All Elements in Two Binary Search Trees

Medium

TreeDepth-First SearchBinary Search TreeSortingBinary TreeTwo PointersIn-order Traversal

LeetCode ↗

Approaches

Brute ForceOptimal

Complexity Comparison

	Brute Force	Optimal Solution★
Time	O(n²)	O(n)
Space	O(n)	O(n)

💡

Intuition

Time O(n)Space O(n)

The optimal solution leverages the properties of binary search trees by performing an in-order traversal to collect elements from both trees and merging them in sorted order without needing a separate sort step.

⚙️

Algorithm

2 steps

1Step 1: Perform in-order traversal on both trees simultaneously.
2Step 2: Use two pointers to merge the two sorted lists into a final sorted list.

solution.py37 lines

1# Full working Python code
2from typing import List
3
4class TreeNode:
5    def __init__(self, val=0, left=None, right=None):
6        self.val = val
7        self.left = left
8        self.right = right
9
10
11def inorder_traversal(root: TreeNode) -> List[int]:
12    stack, result = [], []
13    while stack or root:
14        while root:
15            stack.append(root)
16            root = root.left
17        root = stack.pop()
18        result.append(root.val)
19        root = root.right
20    return result
21
22
23def getAllElements(root1: TreeNode, root2: TreeNode) -> List[int]:
24    list1 = inorder_traversal(root1)
25    list2 = inorder_traversal(root2)
26    merged = []
27    i, j = 0, 0
28    while i < len(list1) and j < len(list2):
29        if list1[i] < list2[j]:
30            merged.append(list1[i])
31            i += 1
32        else:
33            merged.append(list2[j])
34            j += 1
35    merged.extend(list1[i:])
36    merged.extend(list2[j:])
37    return merged

ℹ

Complexity note: The time complexity is O(n) because we traverse each tree once and merge the results in linear time. The space complexity is O(n) due to storing the elements in lists.

1In-order traversal of BSTs gives sorted elements.
2Merging two sorted lists can be done efficiently with two pointers.

Solutions and explanations are original Tejav content. Problem titles © LeetCode — use the LeetCode button above for the full problem statement.