All Elements In Two Binary Search Trees - Leetcode Solution

The problem "All Elements In Two Binary Search Trees" on LeetCode asks us to find the sorted list of all elements from two given binary search trees.

The basic idea of the solution is to perform an in-order traversal of both the trees and merge the sorted results. Since both of the trees are binary search trees, the in-order traversal would result in a sorted sequence of elements in each tree.

Algorithm:

1. Create an empty list to store the result.
2. Traverse the first tree in in-order and add each element to the list.
3. Traverse the second tree in in-order and add each element to the list.
4. Merge the two sorted lists into a single sorted list.
5. Return the final sorted list.

Code:

def merge_lists(lst1, lst2):
    i, j = 0, 0
    res = []
    while i < len(lst1) and j < len(lst2):
        if lst1[i] < lst2[j]:
            res.append(lst1[i])
            i += 1
        else:
            res.append(lst2[j])
            j += 1
    res.extend(lst1[i:])
    res.extend(lst2[j:])
    return res

def inorder_traversal(root, lst):
    if root is None:
        return
    inorder_traversal(root.left, lst)
    lst.append(root.val)
    inorder_traversal(root.right, lst)

def getAllElements(root1: TreeNode, root2: TreeNode) -> List[int]:
    lst1, lst2 = [], []
    inorder_traversal(root1, lst1)
    inorder_traversal(root2, lst2)
    return merge_lists(lst1, lst2)

The merge_lists function takes two sorted lists and merges them into a new sorted list. We use two pointers i and j to keep track of the indices of the two lists as we traverse them. We compare the elements at the current indices of both lists and append the smaller element to the result list. We increment the pointer of the list from which the smaller element was appended. Finally, we append any remaining elements from the two lists to the result list.

The inorder_traversal function performs the in-order traversal of a binary search tree and adds the elements to a list. We first traverse the left subtree recursively, then append the current node value, and then traverse the right subtree recursively.

The getAllElements function is the main function that takes the two root nodes as inputs and returns a sorted list of all elements in the two binary search trees. We first create two empty lists lst1 and lst2. We then perform the in-order traversal of both trees using the inorder_traversal function and add the elements to their respective lists. Finally, we merge the two sorted lists using the merge_lists function and return the result.

1