LeetCode Solutions Blog

All Elements in Two Binary Search Trees

Number: 1427

Difficulty: Medium

Paid? No

Problem Description

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

Key Insights

In-order traversal of a BST produces a sorted list.
Perform in-order traversal on both trees separately.
Merge the two sorted lists into one sorted list.
Handle edge cases where one or both trees might be empty.

Space and Time Complexity

Time Complexity: O(n1 + n2), where n1 and n2 are the number of nodes in root1 and root2 respectively, due to performing in-order traversals and merging. Space Complexity: O(n1 + n2) for storing the elements from both trees.

Solution

The solution involves two main steps:

Traverse each binary search tree using an in-order traversal to get a sorted list of values.
Merge the two sorted lists using the two-pointer technique to produce one final sorted list.

Data Structures and Algorithms used:

Recursion for in-order traversal.
Two-pointer technique for merging two sorted arrays. This approach efficiently leverages the BST property and sorting of individual traversals.

Code Solutions

# Define the TreeNode class for clarity.
class TreeNode:
    def __init__(self, val=0, left=None, right=None):
        self.val = val
        self.left = left
        self.right = right

# Function to perform in-order traversal on a BST.
def inorder_traversal(node, output):
    # Base case: if node is None, just return.
    if not node:
        return
    # Traverse the left subtree.
    inorder_traversal(node.left, output)
    # Process the current node.
    output.append(node.val)
    # Traverse the right subtree.
    inorder_traversal(node.right, output)

def getAllElements(root1, root2):
    # Obtain sorted list of elements from both trees.
    list1, list2 = [], []
    inorder_traversal(root1, list1)  # In-order traversal for root1.
    inorder_traversal(root2, list2)  # In-order traversal for root2.

    # Merge two sorted lists.
    merged_list = []
    i, j = 0, 0
    # Use two pointers to merge lists.
    while i < len(list1) and j < len(list2):
        if list1[i] <= list2[j]:
            merged_list.append(list1[i])
            i += 1
        else:
            merged_list.append(list2[j])
            j += 1
    # Append remaining elements if any.
    merged_list.extend(list1[i:])
    merged_list.extend(list2[j:])
    return merged_list

# Example usage:
# root1 = TreeNode(2, TreeNode(1), TreeNode(4))
# root2 = TreeNode(1, TreeNode(0), TreeNode(3))
# print(getAllElements(root1, root2))  # Output should be [0,1,1,2,3,4]