Abstract / Summary

Combine the elements from two binary search trees into a single sorted list.

Note

The full problem description, including helpful examples, can be found on LeetCode.

This problem is ranked as

and has an acceptance rate of about 80% (200k+ submissions).

Typical patterns to solve this problem:

• Binary Search Tree
• Binary Tree
• Depth First Search
• Sorting
• Tree

Every single line of code was written by me, 100% from scratch, between August 2023 and August 2024.
However, two years later I set up this website and used various AI tools to generate most of the walkthrough / explanations below.

See this dedicated page for more details.

Overview

The provided implementation defines a class Solution with a single public method getAllElements. The method receives two binary-tree roots, traverses each tree, aggregates every node value into a single list, and finally returns the list in ascending order. The algorithm is straightforward: a depth-first traversal collects values, and Python’s built-in sorting routine produces the ordered result.

Key Steps

Allocation of the aggregation container

all = []

A mutable list named all is created in the outer scope of the method. This list serves as the shared collection point for values discovered during the traversal of both input trees. Because the list is defined once, the subsequent recursive calls simply append to the same object, avoiding the overhead of repeatedly allocating intermediate containers.

Definition of the recursive traversal

def deeper(node):
    if node:
        deeper(node.left)
        deeper(node.right)
        all.append(node.val)

A nested function deeper is declared inside getAllElements. It captures the outer all list via a closure, allowing direct mutation without passing the list as an argument. The function checks whether the current node reference is non-null; if it is, the function recurses on the left child, then on the right child, and finally appends the node’s value to all. This order corresponds to a post-order traversal, but the specific ordering of insertion is irrelevant because the final step sorts the accumulated values.

Invocation of the traversal on both trees

deeper(root1)
deeper(root2)

The deeper function is called sequentially for each of the two input roots. If either root is None, the guard inside deeper prevents any further recursion, effectively handling empty-tree scenarios without additional conditional logic.

Sorting and returning the result

return sorted(all)

After both traversals have completed, the built-in sorted function is applied to the all list. Python’s Timsort algorithm efficiently handles partially ordered data, which can be advantageous when the input trees already contain sorted sequences. The sorted list is then returned as the final output.

Edge Cases Handled

When both root1 and root2 are None, the deeper calls encounter a falsy node immediately, perform no recursion, and leave all empty. The subsequent sorted call on an empty list yields another empty list, which correctly represents the union of two empty trees.

If only one of the roots is None, the traversal proceeds solely on the non-null tree. The guard inside deeper ensures that the null tree contributes no values, while the other tree’s values are collected and sorted as usual.

Duplicate values that appear in either or both trees are appended each time they are encountered. The final sorted list therefore contains repeated entries, preserving the multiset semantics required by the problem specification.

Trees of varying depths are accommodated because the recursion depth is bounded by the height of each individual tree. The algorithm does not assume any balance property; it will correctly traverse highly skewed trees, as the guard if node: prevents attempts to access attributes of a null reference.

Performance Optimizations Observed

The use of a single mutable list all eliminates the need for concatenating intermediate results from separate recursive calls. This in-place accumulation reduces memory churn and improves cache locality, as all appended values reside in a contiguous memory region.

Capturing all via a closure avoids passing the list as an explicit argument through each recursive layer. This design choice reduces the overhead of argument handling on the call stack and keeps the recursive signature minimal.

Relying on Python’s native sorted function leverages the highly optimized Timsort algorithm, which adapts to existing order in the data. When the two input trees are themselves binary search trees, the post-order collection may produce a partially ordered sequence, allowing Timsort to run faster than a generic O(n log n) sort.

The recursion follows a post-order pattern, which ensures that child nodes are processed before their parent. Although the final ordering is determined by sorting, this traversal order can be beneficial for certain memory access patterns, as it tends to visit deeper nodes first, potentially improving branch prediction on modern CPUs.

Overall, the implementation balances simplicity with effective use of Python’s built-in data structures and algorithms, delivering a solution that is both concise and performant for the intended task.

Imagine there are two large bags of numbered building blocks. Each bag is shaped like a branching tree, with a bigger block at the top and smaller branches leading to other blocks below.

To collect all the numbers, a little helper starts at the top of the first bag. It travels down to the very bottom, hopping over to the left side and then the right side, picking up every block it finds and putting them into a big empty box. It does this for the first bag and then does the exact same thing for the second bag.

Once every single block from both bags is sitting inside the big box in a messy pile, the computer looks at all the numbers. It rearranges them so that the smallest numbers are at the front and the biggest numbers are at the back, just like lining up toys from smallest to largest.

Several LLMs ranked my code quality on a scale from 1 (very poor) to 10 (outstanding):

Time: loglinear
As a rule of thumb, the maximum input size for one second execution time is

• factorial: up to 10 elements
• exponential: up to 20 elements
• polynomial: a few thousand elements
• loglinear: up to 100,000 elements
• linear: a few million elements
• logarithmic: a billion elements
• constant: practically unlimited

I wrote a basic crawler to find other solutions to that problem.
Obviously, I did that after I solved the problem myself.

In general, AlgoMonster and WalkCCC solutions are high-quality and always worth a look.
I haven't checked most of the other solutions, but they might be helpful as well.

And of course, the LeetCode forum is always a good place (or even the best) to look for alternative approaches.

(click on a column header to sort the table)

	author
author	solutions
www	AlgoMonster	C++	Python	Java						TS
	WalkCCC	C++		Java
	leetcode.ca	C++	Python	Java				Go	Rust	TS
	MemoryLimitExceeded	C++	Python
	Progiez	C++	Python	Java
github	BigEggStudy					C#
	black-shadows	C++
	charles-wangkai			Java
	everthis				JS
	fartem						Ruby
	FelixFan1122			Java
	fpdjsns	C++
	fsq	C++
	halfrost							Go
	JoshCrozier				JS
	keineahnung2345	C++
	lkwq007		Python
	suxrobGM					C#
	trung-hn		Python
	varunu28			Java
	YuriSpiridonov		Python
AlgoMonster	C++, Python, Java, TypeScript
WalkCCC	C++, Java
leetcode.ca	C++, Go, Java, Python, Rust, TypeScript
MemoryLimitExceeded	Python, C++
Progiez	C++, Java, Python
BigEggStudy	C#
black-shadows	C++, C++
charles-wangkai	Java
everthis	JavaScript
fartem	Ruby
FelixFan1122	Java
fpdjsns	C++
fsq	C++
halfrost	Go
JoshCrozier	JavaScript
keineahnung2345	C++
lkwq007	Python
suxrobGM	C#
trung-hn	Python
varunu28	Java
YuriSpiridonov	Python

There are a few extra pages giving you some insights into my setup:

• Tech Stack - my development environment and tools
• AI - how AI helped me create this website (NOT solving the problems)
• Progress - progression over time
• Quality - code quality