Is All Elements in Two Binary Search Trees easy or hard?

The problem is generally classified as Medium. Understanding BST in-order traversal is straightforward, but combining traversal with an efficient merge or implementing simultaneous stack-based traversal requires solid algorithm fundamentals.

How to solve All Elements in Two Binary Search Trees in O(n)?

Use in-order traversal to extract sorted values from both BSTs and merge them using two pointers. Since each node is processed once and the merge step is linear, the total runtime becomes O(n + m). A stack-based simultaneous traversal can also achieve the same complexity while reducing memory usage.

What is the best approach for All Elements in Two Binary Search Trees?

The most practical approach is performing in-order traversal on both BSTs and then merging the two sorted arrays. Each traversal produces sorted values because of the BST property, and merging them takes linear time. The total complexity is O(n + m) time and O(n + m) space.

What data structure is used in All Elements in Two Binary Search Trees?

The problem uses Binary Search Trees and relies on in-order traversal. Some solutions store values in arrays for merging, while optimized approaches use stacks to simulate iterative traversal of both trees.

What is the time complexity of All Elements in Two Binary Search Trees?

The optimal time complexity is O(n + m), where n and m are the number of nodes in the two trees. Each node is visited exactly once during traversal, and the merge step processes each element once as well.

All Elements in Two Binary Search Trees Python or Java solution approach?

In Python or Java, the typical solution performs recursive or iterative in-order traversal to build two sorted lists, then merges them using two pointers. Both languages can also implement the optimized stack-based traversal to reduce auxiliary space.

Is All Elements in Two Binary Search Trees asked at Google, Amazon, or Meta?

BST traversal and merging problems frequently appear in interviews at companies like Amazon, Google, and Meta. Variants involving in-order traversal, merging sorted structures, or two-pointer techniques are common in technical interviews.

Description Hints 2 Solution Video 22:33

1305. All Elements in Two Binary Search Trees

Medium80.5% acceptance2 companies

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

Example 1:

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

Example 2:

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

Constraints:

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

Asked at 2 companies

Amazon Meta

Topics

Hints open one at a time

Hint 1

Traverse the first tree in list1 and the second tree in list2.

Hint 2

Merge the two trees in one list and sort it.

22:33

Still stuck?Read 3 approaches, or watch a walkthrough.

Open solution

LanguageLoading editor…

1# Definition for a binary tree node.
2# class TreeNode:
3#     def __init__(self, val=0, left=None, right=None):
4#         self.val = val
5#         self.left = left
6#         self.right = right
7class Solution:
8    def getAllElements(self, root1: Optional[TreeNode], root2: Optional[TreeNode]) -> List[int]:
9        

Starter codePython 3Spaces: 4

Examples

Case 1Case 2

Input

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

Input

[1,null,8]
[8,1]

Your code is saved on this device.Solution