LeetCode 1305 - All Elements in Two Binary Search Trees

The problem gives us two binary search trees, root1 and root2. A binary search tree, commonly abbreviated as BST, has the important property that for every node: - All values in the left subtree are smaller than the node's value - All values in the right subtree are larger…

leetcodemediumtreedepth-first-searchbinary-search-treesortingbinary-tree

LeetCode Problem 1305

Difficulty: 🟡 Medium
Topics: Tree, Depth-First Search, Binary Search Tree, Sorting, Binary Tree

Solution

Problem Understanding

The problem gives us two binary search trees, root1 and root2. A binary search tree, commonly abbreviated as BST, has the important property that for every node:

  • All values in the left subtree are smaller than the node's value
  • All values in the right subtree are larger than the node's value

We need to collect every integer stored in both trees and return them in one sorted list in ascending order.

The key detail is that the input trees are already BSTs. That means each tree individually contains values that can be retrieved in sorted order by performing an inorder traversal. An inorder traversal visits nodes in this order:

  1. Left subtree
  2. Current node
  3. Right subtree

For a BST, this traversal naturally produces sorted values.

The input consists of two tree roots. Either tree may be empty, represented by None in Python or nil in Go. The output must contain every value from both trees, including duplicates, sorted from smallest to largest.

The constraints tell us that each tree can contain up to 5000 nodes. This size is large enough that we should avoid unnecessarily expensive sorting operations if we can leverage BST properties directly. However, it is still small enough that linear or near-linear algorithms are perfectly acceptable.

Several edge cases are important:

  • One or both trees may be empty
  • Trees may contain duplicate values across the two trees
  • Trees may be extremely unbalanced, effectively behaving like linked lists
  • Negative values are allowed
  • One tree may contain significantly more nodes than the other

A naive implementation that ignores BST ordering would miss an opportunity for optimization.

Approaches

Brute Force Approach

The most straightforward solution is to collect all values from both trees into one array, then sort the final array.

We can traverse each tree using any traversal method, such as preorder or inorder, because the brute-force approach does not rely on BST ordering. After gathering every value, we use a standard sorting algorithm to sort the combined list.

This approach is correct because it eventually places every value into the array, and sorting guarantees ascending order.

However, it performs unnecessary work. Since BSTs already contain ordered structure, sorting again wastes computation.

If the total number of nodes is n, sorting requires O(n log n) time.

Optimal Approach

The important insight is that inorder traversal of a BST already produces values in sorted order.

Instead of collecting unsorted values and sorting afterward, we can:

  1. Perform inorder traversal on both trees separately
  2. Obtain two individually sorted arrays
  3. Merge the two sorted arrays using the same technique used in merge sort

This avoids the extra sorting step.

The merge process is linear because both arrays are already sorted. At each step, we compare the current elements from both arrays and append the smaller one.

This gives an overall linear-time solution.

Approach Time Complexity Space Complexity Notes
Brute Force O(n log n) O(n) Collect all elements and sort afterward
Optimal O(n) O(n) Use inorder traversal plus linear merge

Here, n represents the total number of nodes across both trees.

Algorithm Walkthrough

Optimal Algorithm

  1. Perform an inorder traversal on the first BST.

During the traversal, recursively visit the left subtree, then the current node, then the right subtree. Because the tree is a BST, this produces values in ascending order. Store these values in an array called values1. 2. Perform an inorder traversal on the second BST.

Use the same traversal strategy and store the results in another sorted array called values2. 3. Initialize two pointers.

Create pointer i for values1 and pointer j for values2. Both start at index 0. 4. Merge the two sorted arrays.

Compare values1[i] and values2[j].

  • If values1[i] is smaller, append it to the result and increment i
  • Otherwise, append values2[j] and increment j

This works because both arrays are already sorted. 5. Process remaining elements.

After one array is exhausted, append all remaining elements from the other array. 6. Return the merged result.

The final merged array contains all elements in ascending order.

Why it works

The correctness relies on two properties:

  • Inorder traversal of a BST always produces sorted values
  • Merging two sorted arrays preserves sorted order

Since every node from both trees appears exactly once in the traversal arrays, and the merge step processes all elements while maintaining order, the final result is guaranteed to contain all values in ascending order.

Python Solution

# 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

from typing import List, Optional

class Solution:
    def getAllElements(
        self,
        root1: Optional[TreeNode],
        root2: Optional[TreeNode]
    ) -> List[int]:

        def inorder(node: Optional[TreeNode], values: List[int]) -> None:
            if not node:
                return

            inorder(node.left, values)
            values.append(node.val)
            inorder(node.right, values)

        values1 = []
        values2 = []

        inorder(root1, values1)
        inorder(root2, values2)

        merged = []
        i = 0
        j = 0

        while i < len(values1) and j < len(values2):
            if values1[i] <= values2[j]:
                merged.append(values1[i])
                i += 1
            else:
                merged.append(values2[j])
                j += 1

        while i < len(values1):
            merged.append(values1[i])
            i += 1

        while j < len(values2):
            merged.append(values2[j])
            j += 1

        return merged

The implementation starts by defining a helper function called inorder. This function recursively traverses the BST in inorder sequence and appends node values into a list.

Two arrays, values1 and values2, store the sorted traversal results from the two trees.

After obtaining both sorted arrays, the algorithm uses two pointers to merge them efficiently. The merge logic is identical to the merge phase of merge sort. Since both arrays are already sorted, comparing the current smallest unused elements guarantees that the next appended element is globally smallest.

Finally, any remaining elements are appended after one array becomes exhausted.

Go Solution

/**
 * Definition for a binary tree node.
 * type TreeNode struct {
 *     Val int
 *     Left *TreeNode
 *     Right *TreeNode
 * }
 */
func getAllElements(root1 *TreeNode, root2 *TreeNode) []int {

    var inorder func(node *TreeNode, values *[]int)

    inorder = func(node *TreeNode, values *[]int) {
        if node == nil {
            return
        }

        inorder(node.Left, values)
        *values = append(*values, node.Val)
        inorder(node.Right, values)
    }

    values1 := []int{}
    values2 := []int{}

    inorder(root1, &values1)
    inorder(root2, &values2)

    merged := []int{}

    i := 0
    j := 0

    for i < len(values1) && j < len(values2) {
        if values1[i] <= values2[j] {
            merged = append(merged, values1[i])
            i++
        } else {
            merged = append(merged, values2[j])
            j++
        }
    }

    for i < len(values1) {
        merged = append(merged, values1[i])
        i++
    }

    for j < len(values2) {
        merged = append(merged, values2[j])
        j++
    }

    return merged
}

The Go version follows the same algorithmic structure as the Python solution. The main implementation difference is that slices are passed by reference during inorder traversal so that recursive calls can append values efficiently.

Go uses nil instead of None for empty nodes. Slice appending is handled using the built-in append function.

There are no integer overflow concerns because node values remain well within Go's standard integer range.

Worked Examples

Example 1

Input:

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

Tree 1:

    2
   / \
  1   4

Tree 2:

    1
   / \
  0   3

Step 1: Inorder traversal of root1

Traversal Step Current Node values1
Visit left of 2 1 [1]
Visit 2 2 [1, 2]
Visit right of 2 4 [1, 2, 4]

Final:

values1 = [1, 2, 4]

Step 2: Inorder traversal of root2

Traversal Step Current Node values2
Visit left of 1 0 [0]
Visit 1 1 [0, 1]
Visit right of 1 3 [0, 1, 3]

Final:

values2 = [0, 1, 3]

Step 3: Merge arrays

i j Compare Append Result
0 0 1 vs 0 0 [0]
0 1 1 vs 1 1 [0, 1]
1 1 2 vs 1 1 [0, 1, 1]
1 2 2 vs 3 2 [0, 1, 1, 2]
2 2 4 vs 3 3 [0, 1, 1, 2, 3]

Remaining element from values1:

4

Final result:

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

Example 2

Input:

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

Tree 1:

1
 \
  8

Tree 2:

  8
 /
1

Traversal Results

Tree Inorder Result
root1 [1, 8]
root2 [1, 8]

Merge Process

Compare Append Result
1 vs 1 1 [1]
8 vs 1 1 [1, 1]
8 vs 8 8 [1, 1, 8]

Append remaining:

8

Final result:

[1,1,8,8]

Complexity Analysis

Measure Complexity Explanation
Time O(n) Each node is visited once, and merging is linear
Space O(n) Arrays store all node values

The inorder traversals collectively visit every node exactly once. If the total number of nodes across both trees is n, traversal requires O(n) time.

The merge step also processes each element exactly once, which is another O(n) operation.

The auxiliary space comes primarily from the traversal arrays and the output array. In the worst case, all node values are stored simultaneously, giving O(n) space usage. Recursive traversal also adds stack space proportional to tree height.

Test Cases

# Helper TreeNode class for testing
class TreeNode:
    def __init__(self, val=0, left=None, right=None):
        self.val = val
        self.left = left
        self.right = right

solution = Solution()

# Example 1
root1 = TreeNode(2, TreeNode(1), TreeNode(4))
root2 = TreeNode(1, TreeNode(0), TreeNode(3))
assert solution.getAllElements(root1, root2) == [0,1,1,2,3,4]  # standard merge case

# Example 2
root1 = TreeNode(1, None, TreeNode(8))
root2 = TreeNode(8, TreeNode(1), None)
assert solution.getAllElements(root1, root2) == [1,1,8,8]  # duplicate values across trees

# Both trees empty
assert solution.getAllElements(None, None) == []  # completely empty input

# One tree empty
root1 = TreeNode(2, TreeNode(1), TreeNode(3))
assert solution.getAllElements(root1, None) == [1,2,3]  # single-tree behavior

# Negative values
root1 = TreeNode(-10, TreeNode(-20), TreeNode(-5))
root2 = TreeNode(-15, None, TreeNode(0))
assert solution.getAllElements(root1, root2) == [-20,-15,-10,-5,0]  # negative number ordering

# Highly unbalanced tree
root1 = TreeNode(1)
root1.right = TreeNode(2)
root1.right.right = TreeNode(3)

root2 = TreeNode(0)

assert solution.getAllElements(root1, root2) == [0,1,2,3]  # linked-list-like BST

# Duplicate values within and across trees
root1 = TreeNode(2, TreeNode(2), TreeNode(2))
root2 = TreeNode(2)
assert solution.getAllElements(root1, root2) == [2,2,2,2]  # repeated values

# Large value range
root1 = TreeNode(100000)
root2 = TreeNode(-100000)
assert solution.getAllElements(root1, root2) == [-100000,100000]  # extreme constraint values
Test Why
Standard balanced trees Validates normal inorder and merge behavior
Duplicate values across trees Ensures duplicates are preserved
Both trees empty Confirms empty input handling
One tree empty Verifies single BST traversal works
Negative values Ensures ordering with negatives
Highly unbalanced tree Tests recursion on skewed structures
Repeated identical values Verifies duplicates are not removed
Extreme value range Confirms constraint boundary handling

Edge Cases

Both Trees Are Empty

A common bug source is forgetting that either tree may be None. If both trees are empty, the traversal arrays remain empty and the merge loop never executes.

The implementation handles this naturally because the inorder traversal immediately returns when given None. The final merged array is simply an empty list.

One Tree Is Much Larger Than the Other

One BST may contain thousands of nodes while the other contains only a few. Incorrect merge logic can accidentally skip remaining elements after one pointer reaches the end.

The implementation avoids this by using two additional loops after the main merge loop. These loops append all remaining elements from whichever array still has unused values.

Highly Unbalanced Trees

A BST can degenerate into a linked-list-like structure if nodes are inserted in sorted order. In this case, recursion depth becomes proportional to the number of nodes.

The algorithm still produces correct output because inorder traversal logic does not depend on tree balance. Even in a skewed tree, visiting left subtree, current node, and right subtree still yields sorted order.