All Elements in Two Binary Search Trees solution and explanation
9 more videos on this problem
All Elements in Two Binary Search Trees | LeetCode 1305 | C++, Java, PythonKnowledge Center · 22:33 · 5K views
All Elements in Two Binary Search Trees | Leetcode 1305 | Binary Search TreeAyushi Sharma · 9:22 · 2K views
all elements in two binary search trees leetcode | leetcode 1305 | bstNaresh Gupta · 8:43 · 1K views
Leetcode 1305: All Elements in Two Binary Search Trees (Leetcode medium, Amazon)Algorithms Casts · 10:27 · 632 views
All Elements in Two Binary Search Trees | Leet code 1305 | Theory explained + Python codeSai Anish Malla · 9:20 · 576 views
Leetcode - All Elements in Two Binary Search Trees (Python)Timothy H Chang · 4:42 · 549 views
All Elements in Two Binary Search Trees | Leetcode September Challenge (Day5) | Leetcode 1305Coding Decoded · 15:37 · 386 views
Daily Leetcode #666: Jan 26, 2022 - 1305. All Elements in Two Binary Search TreesProgramming Live with Larry · 32:52 · 277 views
All Elements in Two Binary Search Trees | LeetCode 1305 | Coders CampCoders Camp · 13:08 · 266 views
All Elements in Two Binary Search Trees Leetcode | Leetcode 1305 | Leetcode september challengeCode Bashers · 8:15 · 199 views
The problem
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]. -105 <= Node.val <= 105
Approach overview
Problem Overview: You are given the roots of two Binary Search Trees. Each BST stores values in sorted order when traversed using in‑order traversal. The task is to return a single sorted list containing every element from both trees.
The key observation: an in-order traversal of a BST already produces a sorted sequence. If you extract the values from both trees in sorted order, the problem becomes identical to merging two sorted arrays.
Approach 1: In-Order Traversal and Merging (Time: O(n + m), Space: O(n + m))
Traverse both trees using in-order traversal from Depth-First Search. Store the result of each traversal in two arrays. Because the trees are BSTs, both arrays are already sorted. Then perform a classic two-pointer merge similar to the merge step of merge sort: compare the current elements from both arrays and append the smaller one to the result. Continue until both arrays are exhausted.
This approach is straightforward and easy to reason about. The traversal step takes O(n) and O(m) for the two trees, and merging takes O(n + m). The tradeoff is memory usage since both arrays store every node value. For most interview scenarios, this solution is perfectly acceptable because of its clarity.
Approach 2: Iterative In-Order Traversal with Stacks (Time: O(n + m), Space: O(h1 + h2))
This method avoids storing the full traversal arrays. Instead, simulate in-order traversal on both trees simultaneously using two stacks. Push left nodes from each tree until you reach the smallest available values. At each step, compare the top nodes of the stacks and pop the smaller one, adding it to the result. After popping a node, move to its right subtree and repeat the left traversal.
This works because each stack always exposes the next smallest element from its tree. Comparing the stack tops effectively mimics the merge step while generating values lazily. The total time remains O(n + m), but extra memory drops to O(h1 + h2), where h1 and h2 are the tree heights.
The algorithm combines concepts from tree traversal and sorted merging. It is especially useful when the trees are large and you want to avoid building full intermediate arrays.
Recommended for interviews: Start with the in-order traversal + merge approach to show you understand BST properties and sorted merging. Then mention the stack-based traversal as an optimization that reduces memory usage while keeping O(n + m) time complexity. Interviewers typically appreciate seeing both approaches and the reasoning behind the tradeoff.
Approach 1: In-Order Traversal and Merging
This approach leverages the in-order traversal property of Binary Search Trees (BSTs), which yields elements in sorted order. We perform an in-order traversal on both trees to extract elements into separate lists. We then merge these two sorted lists into one sorted list.
class TreeNode:
def __init__(self, x):
self.val = x
self.left = None
self.right = None
class Solution:
def getAllElements(self, root1, root2):
def inOrder(node):
return inOrder(node.left) + [node.val] + inOrder(node.right) if node else []
list1, list2 = inOrder(root1), inOrder(root2)
return sorted(list1 + list2)import java.util.ArrayList;
import java.util.List;
public class Solution {
public List<Integer> getAllElements(TreeNode root1, TreeNode root2) {
List<Integer> list1 = new ArrayList<>();
List<Integer> list2 = new ArrayList<>();
inOrder(root1, list1);
inOrder(root2, list2);
return mergeSortedLists(list1, list2);
}
private void inOrder(TreeNode root, List<Integer> list) {
if (root == null) return;
inOrder(root.left, list);
list.add(root.val);
inOrder(root.right, list);
}
private List<Integer> mergeSortedLists(List<Integer> list1, List<Integer> list2) {
List<Integer> merged = new ArrayList<>();
int i = 0, j = 0;
while (i < list1.size() && j < list2.size()) {
if (list1.get(i) < list2.get(j))
merged.add(list1.get(i++));
else
merged.add(list2.get(j++));
}
while (i < list1.size())
merged.add(list1.get(i++));
while (j < list2.size())
merged.add(list2.get(j++));
return merged;
}
public static class TreeNode {
int val;
TreeNode left;
TreeNode right;
TreeNode(int x) { val = x; }
}
}#include <vector>
#include <queue>
using namespace std;
struct TreeNode {
int val;
TreeNode *left;
TreeNode *right;
TreeNode(int x) : val(x), left(NULL), right(NULL) {}
};
void inOrder(TreeNode* root, vector<int>& result) {
if (!root) return;
inOrder(root->left, result);
result.push_back(root->val);
inOrder(root->right, result);
}
vector<int> mergeSortedLists(vector<int>& list1, vector<int>& list2) {
vector<int> merged;
int i = 0, j = 0;
while (i < list1.size() && j < list2.size()) {
if (list1[i] < list2[j])
merged.push_back(list1[i++]);
else
merged.push_back(list2[j++]);
}
while (i < list1.size())
merged.push_back(list1[i++]);
while (j < list2.size())
merged.push_back(list2[j++]);
return merged;
}
vector<int> getAllElements(TreeNode* root1, TreeNode* root2) {
vector<int> list1, list2;
inOrder(root1, list1);
inOrder(root2, list2);
return mergeSortedLists(list1, list2);
}function TreeNode(val, left = null, right = null) {
this.val = (val===undefined ? 0 : val)
this.left = (left===undefined ? null : left)
this.right = (right===undefined ? null : right)
}
var getAllElements = function(root1, root2) {
const inOrder = (node) => node ? [...inOrder(node.left), node.val, ...inOrder(node.right)] : [];
const list1 = inOrder(root1);
const list2 = inOrder(root2);
let merged = [], i = 0, j = 0;
while (i < list1.length && j < list2.length) {
if (list1[i] < list2[j])
merged.push(list1[i++]);
else
merged.push(list2[j++]);
}
return merged.concat(list1.slice(i)).concat(list2.slice(j));
};#include <stdio.h>
#include <stdlib.h>
typedef struct TreeNode {
int val;
struct TreeNode *left;
struct TreeNode *right;
} TreeNode;
void inOrder(TreeNode* root, int* arr, int* returnSize) {
if (root == NULL)
return;
inOrder(root->left, arr, returnSize);
arr[(*returnSize)++] = root->val;
inOrder(root->right, arr, returnSize);
}
int* merge(int* list1, int size1, int* list2, int size2, int* returnSize) {
int* result = (int*)malloc((size1 + size2) * sizeof(int));
*returnSize = 0;
int i = 0, j = 0;
while (i < size1 && j < size2) {
if (list1[i] < list2[j])
result[(*returnSize)++] = list1[i++];
else
result[(*returnSize)++] = list2[j++];
}
while (i < size1)
result[(*returnSize)++] = list1[i++];
while (j < size2)
result[(*returnSize)++] = list2[j++];
return result;
}
int* getAllElements(TreeNode* root1, TreeNode* root2, int* returnSize) {
int list1[5000], list2[5000];
int size1 = 0, size2 = 0;
inOrder(root1, list1, &size1);
inOrder(root2, list2, &size2);
return merge(list1, size1, list2, size2, returnSize);
}using System;
using System.Collections.Generic;
public class TreeNode {
public int val;
public TreeNode left;
public TreeNode right;
public TreeNode(int x) { val = x; }
}
public class Solution {
public IList<int> GetAllElements(TreeNode root1, TreeNode root2) {
List<int> list1 = new List<int>();
List<int> list2 = new List<int>();
InOrder(root1, list1);
InOrder(root2, list2);
return MergeSortedLists(list1, list2);
}
private void InOrder(TreeNode node, List<int> list) {
if (node == null) return;
InOrder(node.left, list);
list.Add(node.val);
InOrder(node.right, list);
}
private List<int> MergeSortedLists(List<int> list1, List<int> list2) {
List<int> merged = new List<int>();
int i = 0, j = 0;
while (i < list1.Count && j < list2.Count) {
if (list1[i] < list2[j])
merged.Add(list1[i++]);
else
merged.Add(list2[j++]);
}
while (i < list1.Count)
merged.Add(list1[i++]);
while (j < list2.Count)
merged.Add(list2[j++]);
return merged;
}
}The Python solution uses an in-order traversal function that returns a list. By leveraging this function, we build sorted lists from both trees and concatenate them before returning the fully sorted list using Python's built-in sorted function.
Time Complexity: O(n + m) for traversal plus sorting time O((n + m) log(n + m)). Space Complexity: O(n + m) for storing elements from both trees.
Approach 2: Iterative In-Order Traversal with Stacks
This approach uses stacks to perform an iterative in-order traversal of both trees simultaneously. We make use of two separate stacks to store the nodes of current branches of the trees. The smallest node from the top of the stacks is chosen and processed to build the result list in sorted order.
class TreeNode:
def __init__(self, x):
self.val = x
self.left = None
self.right = None
class Solution:
def getAllElements(self, root1, root2):
stack1, stack2, result = [], [], []
while root1 or root2 or stack1 or stack2:
while root1:
stack1.append(root1)
root1 = root1.left
while root2:
stack2.append(root2)
root2 = root2.left
if not stack2 or (stack1 and stack1[-1].val <= (stack2[-1]).val):
root1 = stack1.pop()
result.append(root1.val)
root1 = root1.right
else:
root2 = stack2.pop()
result.append(root2.val)
root2 = root2.right
return resultimport java.util.ArrayList;
import java.util.List;
import java.util.Stack;
public class Solution {
public List<Integer> getAllElements(TreeNode root1, TreeNode root2) {
List<Integer> result = new ArrayList<>();
Stack<TreeNode> stack1 = new Stack<>();
Stack<TreeNode> stack2 = new Stack<>();
while (root1 != null || root2 != null || !stack1.isEmpty() || !stack2.isEmpty()) {
while (root1 != null) {
stack1.push(root1);
root1 = root1.left;
}
while (root2 != null) {
stack2.push(root2);
root2 = root2.left;
}
if (stack2.isEmpty() || (!stack1.isEmpty() && stack1.peek().val <= stack2.peek().val)) {
root1 = stack1.pop();
result.add(root1.val);
root1 = root1.right;
} else {
root2 = stack2.pop();
result.add(root2.val);
root2 = root2.right;
}
}
return result;
}
public static class TreeNode {
int val;
TreeNode left;
TreeNode right;
TreeNode(int x) { val = x; }
}
}#include <vector>
#include <stack>
using namespace std;
struct TreeNode {
int val;
TreeNode *left;
TreeNode *right;
TreeNode(int x) : val(x), left(NULL), right(NULL) {}
};
vector<int> getAllElements(TreeNode* root1, TreeNode* root2) {
vector<int> result;
stack<TreeNode*> s1, s2;
while (root1 || root2 || !s1.empty() || !s2.empty()) {
while (root1) {
s1.push(root1);
root1 = root1->left;
}
while (root2) {
s2.push(root2);
root2 = root2->left;
}
if (s2.empty() || (!s1.empty() && s1.top()->val <= s2.top()->val)) {
root1 = s1.top(); s1.pop();
result.push_back(root1->val);
root1 = root1->right;
} else {
root2 = s2.top(); s2.pop();
result.push_back(root2->val);
root2 = root2->right;
}
}
return result;
}function TreeNode(val, left = null, right = null) {
this.val = (val===undefined ? 0 : val)
this.left = (left===undefined ? null : left)
this.right = (right===undefined ? null : right)
}
var getAllElements = function(root1, root2) {
let stack1 = [], stack2 = [], result = [];
while (root1 || root2 || stack1.length > 0 || stack2.length > 0) {
while (root1) {
stack1.push(root1);
root1 = root1.left;
}
while (root2) {
stack2.push(root2);
root2 = root2.left;
}
let val1 = (!stack1.length) ? Number.MAX_SAFE_INTEGER : stack1[stack1.length-1].val;
let val2 = (!stack2.length) ? Number.MAX_SAFE_INTEGER : stack2[stack2.length-1].val;
if (val1 <= val2) {
root1 = stack1.pop();
result.push(root1.val);
root1 = root1.right;
} else {
root2 = stack2.pop();
result.push(root2.val);
root2 = root2.right;
}
}
return result;
};#include <stdio.h>
#include <stdlib.h>
typedef struct TreeNode {
int val;
struct TreeNode *left;
struct TreeNode *right;
} TreeNode;
typedef struct Stack {
TreeNode **arr;
int top;
} Stack;
Stack* createStack(int size) {
Stack *stack = (Stack *)malloc(sizeof(Stack));
stack->arr = (TreeNode **)malloc(size * sizeof(TreeNode *));
stack->top = -1;
return stack;
}
void push(Stack *stack, TreeNode *node) {
stack->arr[++stack->top] = node;
}
TreeNode* pop(Stack *stack) {
return stack->arr[stack->top--];
}
int isEmpty(Stack *stack) {
return stack->top == -1;
}
int* getAllElements(TreeNode* root1, TreeNode* root2, int* returnSize) {
int* result = (int *)malloc(10000 * sizeof(int));
*returnSize = 0;
Stack *stack1 = createStack(5000);
Stack *stack2 = createStack(5000);
while (root1 || root2 || !isEmpty(stack1) || !isEmpty(stack2)) {
while (root1) {
push(stack1, root1);
root1 = root1->left;
}
while (root2) {
push(stack2, root2);
root2 = root2->left;
}
if (isEmpty(stack2) || (!isEmpty(stack1) && stack1->arr[stack1->top]->val <= stack2->arr[stack2->top]->val)) {
root1 = pop(stack1);
result[(*returnSize)++] = root1->val;
root1 = root1->right;
} else {
root2 = pop(stack2);
result[(*returnSize)++] = root2->val;
root2 = root2->right;
}
}
free(stack1->arr);
free(stack1);
free(stack2->arr);
free(stack2);
return result;
}using System.Collections.Generic;
public class TreeNode {
public int val;
public TreeNode left;
public TreeNode right;
public TreeNode(int x) { val = x; }
}
public class Solution {
public IList<int> GetAllElements(TreeNode root1, TreeNode root2) {
List<int> result = new List<int>();
Stack<TreeNode> stack1 = new Stack<TreeNode>();
Stack<TreeNode> stack2 = new Stack<TreeNode>();
while (root1 != null || root2 != null || stack1.Count > 0 || stack2.Count > 0) {
while (root1 != null) {
stack1.Push(root1);
root1 = root1.left;
}
while (root2 != null) {
stack2.Push(root2);
root2 = root2.left;
}
if (stack2.Count == 0 || (stack1.Count > 0 && stack1.Peek().val <= stack2.Peek().val)) {
root1 = stack1.Pop();
result.Add(root1.val);
root1 = root1.right;
} else {
root2 = stack2.Pop();
result.Add(root2.val);
root2 = root2.right;
}
}
return result;
}
}The Python approach operates using two stacks, simulating an in-order traversal without resorting to function-stack based recursion. This organizes traversals node by node, evaluating each tree's progression state to maintain consistently sorted final results with reactive in-scene processing efficiency.
Time Complexity: O(n + m), cumulative per node operation, buffered only minimally by stack accommodation. Space Complexity: O(h1 + h2) when evaluating stack depths directly influenced by tree heights.
Approach 3: DFS + Merge
Since both trees are binary search trees, we can obtain the node value sequences a and 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.
The time complexity is O(n+m), and the space complexity is O(n+m). Here, n and m are the number of nodes in the two trees, respectively.
/**
* Definition for a binary tree node.
* class TreeNode {
* val: number
* left: TreeNode | null
* right: TreeNode | null
* constructor(val?: number, left?: TreeNode | null, right?: TreeNode | null) {
* this.val = (val===undefined ? 0 : val)
* this.left = (left===undefined ? null : left)
* this.right = (right===undefined ? null : right)
* }
* }
*/
function getAllElements(root1: TreeNode | null, root2: TreeNode | null): number[] {
const dfs = (root: TreeNode | null, nums: number[]) => {
if (!root) {
return;
}
dfs(root.left, nums);
nums.push(root.val);
dfs(root.right, nums);
};
const a: number[] = [];
const b: number[] = [];
dfs(root1, a);
dfs(root2, b);
const [m, n] = [a.length, b.length];
const ans: number[] = [];
let [i, j] = [0, 0];
while (i < m && j < n) {
if (a[i] < b[j]) {
ans.push(a[i++]);
} else {
ans.push(b[j++]);
}
}
while (i < m) {
ans.push(a[i++]);
}
while (j < n) {
ans.push(b[j++]);
}
return ans;
}/**
* Definition for a binary tree node.
* type TreeNode struct {
* Val int
* Left *TreeNode
* Right *TreeNode
* }
*/
func getAllElements(root1 *TreeNode, root2 *TreeNode) (ans []int) {
var dfs func(*TreeNode, *[]int)
dfs = func(root *TreeNode, nums *[]int) {
if root == nil {
return
}
dfs(root.Left, nums)
*nums = append(*nums, root.Val)
dfs(root.Right, nums)
}
a, b := []int{}, []int{}
dfs(root1, &a)
dfs(root2, &b)
i, j := 0, 0
m, n := len(a), len(b)
for i < m && j < n {
if a[i] < b[j] {
ans = append(ans, a[i])
i++
} else {
ans = append(ans, b[j])
j++
}
}
for ; i < m; i++ {
ans = append(ans, a[i])
}
for ; j < n; j++ {
ans = append(ans, b[j])
}
return
}// Definition for a binary tree node.
// #[derive(Debug, PartialEq, Eq)]
// pub struct TreeNode {
// pub val: i32,
// pub left: Option<Rc<RefCell<TreeNode>>>,
// pub right: Option<Rc<RefCell<TreeNode>>>,
// }
//
// impl TreeNode {
// #[inline]
// pub fn new(val: i32) -> Self {
// TreeNode {
// val,
// left: None,
// right: None
// }
// }
// }
use std::cell::RefCell;
use std::rc::Rc;
impl Solution {
pub fn get_all_elements(
root1: Option<Rc<RefCell<TreeNode>>>,
root2: Option<Rc<RefCell<TreeNode>>>,
) -> Vec<i32> {
let mut a = Vec::new();
let mut b = Vec::new();
Solution::dfs(&root1, &mut a);
Solution::dfs(&root2, &mut b);
let mut ans = Vec::new();
let (mut i, mut j) = (0, 0);
while i < a.len() && j < b.len() {
if a[i] <= b[j] {
ans.push(a[i]);
i += 1;
} else {
ans.push(b[j]);
j += 1;
}
}
while i < a.len() {
ans.push(a[i]);
i += 1;
}
while j < b.len() {
ans.push(b[j]);
j += 1;
}
ans
}
fn dfs(root: &Option<Rc<RefCell<TreeNode>>>, nums: &mut Vec<i32>) {
if let Some(node) = root {
let node = node.borrow();
Solution::dfs(&node.left, nums);
nums.push(node.val);
Solution::dfs(&node.right, nums);
}
}
}Complexity comparison
| Approach | Complexity |
|---|---|
| In-Order Traversal and Merging | Time Complexity: O(n + m) for traversal plus sorting time O((n + m) log(n + m)). Space Complexity: O(n + m) for storing elements from both trees. |
| Iterative In-Order Traversal with Stacks | Time Complexity: O(n + m), cumulative per node operation, buffered only minimally by stack accommodation. Space Complexity: O(h1 + h2) when evaluating stack depths directly influenced by tree heights. |
| DFS + Merge | – |
Complexity analysis
| Approach | Time | Space | When to Use |
|---|---|---|---|
| In-Order Traversal and Merge Arrays | O(n + m) | O(n + m) | Best for clarity and interviews when memory is not a concern |
| Iterative In-Order Traversal with Two Stacks | O(n + m) | O(h1 + h2) | When trees are large and you want to avoid storing full traversal arrays |
Frequently asked questions
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.