Introduction

In this blog post, we will explore how to solve the LeetCode problem "1305" using AI. LeetCode is a popular platform for preparing for coding interviews, and with the help of AI tools like Chatmagic, we can generate solutions quickly and efficiently - helping you pass the interviews and get the job offer without having to study for months.

Problem Statement

Given two binary search trees root1 and root2, return a list containing all the integers from both trees sorted in ascending order. Example 1: Input: root1 = [2,1,4], root2 = [1,0,3] Output: [0,1,1,2,3,4] Example 2: Input: root1 = [1,null,8], root2 = [8,1] Output: [1,1,8,8] Constraints: The number of nodes in each tree is in the range [0, 5000]. -105 <= Node.val <= 105

Explanation

Here's a solution to efficiently merge two binary search trees into a sorted list:

• Inorder Traversal: Perform inorder traversals on both BSTs to extract their elements into sorted lists. Inorder traversal visits the left subtree, then the node itself, and then the right subtree, thus naturally producing a sorted sequence for a BST.

• Merge Sorted Lists: Merge the two sorted lists obtained from the traversals into a single sorted list. This can be done efficiently using a standard merge algorithm (similar to merge sort).

• Runtime Complexity: O(n + m) - where n and m are the number of nodes in root1 and root2 respectively.

• Storage Complexity: O(n + m) - primarily due to the space required to store the inorder traversals and the merged list.

Code

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

def getAllElements(root1: TreeNode, root2: TreeNode) -> list[int]:
    """
    Merges two binary search trees into a single sorted list.
    """

    def inorder_traversal(root: TreeNode) -> list[int]:
        """Performs inorder traversal to return a sorted list of node values."""
        result = []
        if root:
            result.extend(inorder_traversal(root.left))
            result.append(root.val)
            result.extend(inorder_traversal(root.right))
        return result

    list1 = inorder_traversal(root1)
    list2 = inorder_traversal(root2)

    merged_list = []
    i, j = 0, 0
    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

    merged_list.extend(list1[i:])
    merged_list.extend(list2[j:])

    return merged_list