Domain 2MediumMEDIUM

All Elements in Two Binary Search Trees

Extract sorted lists via in-order traversal and merge using two pointers to achieve linear time complexity.

Domain: medium•Updated: 2026-09-14
#Iterative Traversal#Stack/Lists#$O(N + M)$ Time Complexity#$O(H_1 + H_2)$ Auxiliary Space

Problem Breakdown

We are given the roots of two Binary Search Trees (BSTs), root1 and root2. The objective is to return a single list containing all integer values from both trees in ascending order.

Key Inputs & Outputs:

  • Inputs: Two tree root nodes (TreeNode). Each node contains an integer value, left child pointer, and right child pointer. Roots can be None (empty).
  • Output: A Python List of integers sorted strictly by value (ascending), preserving duplicates found across both trees.

Constraints & Edge Cases:

  1. Empty Trees: One or both roots may be None. The solution must handle empty inputs gracefully, returning the elements from the non-empty tree or an empty list if both are null.
  2. Duplicates: Values can appear in multiple nodes within a single tree and/or across different trees. All instances must be included in the output.
  3. Negative Numbers: Node values range between -10^5 and 10^5. Sorting logic remains valid regardless of sign.
  4. Tree Shape: Trees can be skewed (worst-case height = N) or balanced. The solution must handle deep recursion depths without stack overflow by using an iterative approach for traversal.

Intuition

A naive brute-force approach would traverse both trees to collect all values into a single list and then sort that combined list using Python’s sort() method.

  • Brute Force Complexity: O((N+M)log⁡(N+M))O((N + M) \log(N + M)), where NN and MM are the number of nodes in each tree.
  • Why it fails optimality: This ignores a critical property: BSTs guarantee that an In-Order Traversal (Left -> Root -> Right) produces values already sorted. We essentially have two pre-sorted streams of data. Sorting them again is redundant work (O(Nlog⁡N)O(N \log N)).

Key Insight: Since we can extract the elements from each tree in sorted order independently, this problem reduces to Merging Two Sorted Arrays. This allows us to achieve linear time complexity O(N+M)O(N + M). We use a Min-Heap or simply two pointers (indices) on the extracted lists. Given Python’s capabilities and clarity requirements for an interview, generating the two sorted arrays first is cleaner than managing iterators/pointers inside tree nodes directly unless we want to optimize space further at the cost of complexity.

Approach

  1. In-Order Traversal: Implement a helper function (iterative using a stack) that traverses root1 and returns all values in ascending order into list A. Do the same for root2 into list B. This leverages BST properties to ensure AA and BB are sorted without explicit sorting logic.
  2. Merge Logic: Initialize two pointers, i = 0 (for list A) and j = 0 (for list B). Create an empty result list.
  3. Comparison Loop: While both lists have elements remaining:
    • Compare A[i] vs B[j].
    • Append the smaller value to the result.
    • Increment the pointer of the list from which we took the element.
  4. Append Remainder: Once one list is exhausted, append all remaining elements from the other list directly (since they are already sorted).

Complexity Analysis

  • Time Complexity: O(N+M)O(N + M).
    • Traversing both trees takes linear time relative to their node counts (NN and MM).
    • The merge step iterates through every element exactly once.
    • Total operations are proportional to the total number of nodes in output.
  • Space Complexity: O(N+M)O(N + M) for the result list (which is required by definition).
    • Auxiliary space: O(H1+H2)O(H_1 + H_2) where HH represents tree height, used by the stack during iterative traversal. In worst-case skewed trees (NN), this becomes O(N)O(N).

Solution

# Definition for a binary tree node.
class TreeNode(object):
    def __init__(self, val=0, left=None, right=None):
        self.val = val
        self.left = left
        self.right = right

from typing import List

class Solution:
    def getAllElements(self, root1: 'TreeNode', root2: 'TreeNode') -> List[int]:
        
        # Helper function to perform iterative In-Order Traversal
        # Returns a list of values in ascending order for the given BST
        def inorder_traverse(node):
            res = []
            stack = []
            
            while node or stack:
                if node:
                    stack.append(node)
                    node = node.left  # Go left as deep as possible
                
                else:
                    node = stack.pop()   # Visit current root of subtree
                    res.append(node.val)
                    node = node.right    # Then go right
                    
            return res

        # Step 1: Extract sorted lists from both trees
        list1 = inorder_traverse(root1)
        list2 = inorder_traverse(root2)
        
        # Step 2 & 3: Merge the two sorted lists using Two Pointers logic
        i, j = 0, 0
        result = []
        
        n1, n2 = len(list1), len(list2)
        
        while i < n1 and j < n2:
            if list1[i] <= list2[j]:
                result.append(list1[i])
                i += 1
            else:
                result.append(list2[j])
                j += 1
        
        # Step 4: Append remaining elements from the non-exhausted tree
        while i < n1:
            result.append(list1[i])
            i += 1
            
        while j < n2:
            result.append(list2[j])
            j += 1
            
        return result