Jobs

Interviews

Discussions

All Elements in Two Binary Search Trees

Medium

Asked by:

16 views

Topics:

TreesArrays

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].
-10⁵ <= Node.val <= 10⁵

Try coding it in LeetCode

All Elements in Two Binary Search Trees

Medium

Asked by:

16 views

Topics:

TreesArrays

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].
-10⁵ <= Node.val <= 10⁵

Try coding it in LeetCode

Solution

Clarifying Questions

When you get asked this question in a real-life environment, it will often be ambiguous (especially at FAANG). Make sure to ask these questions in that case:

What is the range of values that the nodes in the trees can have? Can they be negative, zero, or floating-point numbers?
Can the trees be empty? What should I return if either or both trees are empty?
Are duplicate values allowed within either of the binary search trees, and if so, how should they be handled in the final sorted list?
Do I need to maintain the relative order of elements that come from the same tree in the final sorted list?
Can I modify the given binary search trees, or should I treat them as immutable?

Brute Force Solution

Approach

The brute force method for combining elements from two sorted trees is straightforward. We extract all the numbers from both trees first. Then, we simply sort all the extracted numbers together to get the final result.

Here's how the algorithm would work step-by-step:

First, take all the numbers out of the first tree and put them into a list.
Next, do the same thing for the second tree; put all its numbers into another list.
Now, combine the two lists into one big list.
Finally, sort the big list so the numbers are in increasing order.

Code Implementation

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

def getAllElementsBruteForce(root1, root2):
    first_tree_elements = []
    second_tree_elements = []

    def inorderTraversal(root, elements_list):
        if root:
            inorderTraversal(root.left, elements_list)
            elements_list.append(root.val)
            inorderTraversal(root.right, elements_list)

    # Extract elements from the first BST
    inorderTraversal(root1, first_tree_elements)

    # Extract elements from the second BST
    inorderTraversal(root2, second_tree_elements)

    combined_elements = first_tree_elements + second_tree_elements

    # Sorting to combine the elements
    combined_elements.sort()

    return combined_elements

Big(O) Analysis

Time Complexity

O(n log n) – The algorithm first traverses both binary search trees to extract all elements. Let n be the total number of nodes in both trees. Extracting the elements from both trees takes O(n) time, where n is the total number of nodes. Then, these elements are combined into a single list, which also takes O(n) time. Finally, the combined list is sorted. The dominant operation here is sorting, which typically uses an algorithm like merge sort or quicksort, resulting in a time complexity of O(n log n). Therefore, the overall time complexity is O(n log n).

Space Complexity

O(N) – The described solution extracts all elements from both binary search trees into two separate lists. Let N represent the total number of nodes across both trees. In the worst case, one tree might have a very small number of nodes, while the other tree has nearly all N nodes. This would result in two lists, the larger of which could hold up to N elements. After combining them, sorting the single large list of size N also requires O(N) auxiliary space in many sorting algorithms (e.g., merge sort used internally). Therefore the auxiliary space complexity is O(N).

Optimal Solution

Approach

The best way to merge two sorted binary search trees is to first extract their elements into sorted lists. Then, we can efficiently merge these two sorted lists into a single sorted list, which represents all elements in ascending order.

Here's how the algorithm would work step-by-step:

Go through the first binary search tree and create a sorted list of all its numbers. Because it is a search tree, we can do this efficiently.
Do the same thing for the second binary search tree: make another sorted list of its numbers.
Now you have two sorted lists. Merge these two lists together into one big sorted list. The merging process should maintain the sorted order.
The final sorted list contains all the elements from both trees in the correct order.

Code Implementation

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

class Solution:
    def getAllElements(self, root1: TreeNode, root2: TreeNode) -> list[int]:
        first_tree_elements = []
        second_tree_elements = []

        def inorder_traversal(root: TreeNode, element_list: list[int]) -> None:
            if root:
                inorder_traversal(root.left, element_list)
                element_list.append(root.val)
                inorder_traversal(root.right, element_list)

        # Traverse the first tree and store elements in sorted order.
        inorder_traversal(root1, first_tree_elements)

        # Traverse the second tree and store elements in sorted order.
        inorder_traversal(root2, second_tree_elements)

        merged_elements = []
        first_index = 0
        second_index = 0

        # Merge the two sorted lists into a single sorted list.
        while first_index < len(first_tree_elements) and second_index < len(second_tree_elements):
            if first_tree_elements[first_index] <= second_tree_elements[second_index]:
                merged_elements.append(first_tree_elements[first_index])
                first_index += 1
            else:
                merged_elements.append(second_tree_elements[second_index])
                second_index += 1

        # Add any remaining elements from the first list.
        while first_index < len(first_tree_elements):
            merged_elements.append(first_tree_elements[first_index])
            first_index += 1

        # Add any remaining elements from the second list.
        while second_index < len(second_tree_elements):
            merged_elements.append(second_tree_elements[second_index])
            second_index += 1

        return merged_elements

Big(O) Analysis

Time Complexity

O(n) – Let n be the total number of nodes in both binary search trees. Step 1 involves traversing the first tree which takes O(n1) time, where n1 is the number of nodes in the first tree. Similarly, Step 2 takes O(n2) time to traverse the second tree, where n2 is the number of nodes in the second tree. Step 3 merges the two sorted lists, which takes O(n1 + n2) = O(n) time. Therefore, the overall time complexity is O(n1) + O(n2) + O(n1 + n2) = O(n).

Space Complexity

O(N) – The space complexity is determined by the two sorted lists created to store the elements of the binary search trees, and the final merged sorted list. In the worst case, both trees could contain close to N/2 elements each, where N is the total number of nodes in both trees combined. Therefore, we require auxiliary space proportional to N to store these lists, resulting in a space complexity of O(N).

Edge Cases

Case	How to Handle
Both trees are empty (null)	Return an empty list as there are no elements to merge.
One tree is empty (null), the other is not	Return the sorted list of elements from the non-empty tree.
Both trees contain only one node	Merge the two single-element lists into a single sorted list.
One tree is extremely large, the other is small	Ensure the merge algorithm avoids excessive recursion or stack overflow issues and considers iterative merging approaches for scalability.
Trees contain duplicate values	The merging process should correctly handle duplicates, preserving all occurrences in the final sorted list.
Trees contain negative, zero, and positive values	The comparison and merging process should correctly order all elements including negative and zero values.
Trees are highly unbalanced or skewed	Inorder traversal should still be efficient, and the merge process should not degrade to quadratic time based on skewness.
Integer overflow during element comparison	Utilize a safe comparison method that avoids direct subtraction or addition to prevent potential overflow errors.

Both trees are empty (null)

How to Handle:

Return an empty list as there are no elements to merge.

One tree is empty (null), the other is not

How to Handle:

Return the sorted list of elements from the non-empty tree.

Both trees contain only one node

How to Handle:

Merge the two single-element lists into a single sorted list.

One tree is extremely large, the other is small

How to Handle:

Ensure the merge algorithm avoids excessive recursion or stack overflow issues and considers iterative merging approaches for scalability.

Trees contain duplicate values

How to Handle:

The merging process should correctly handle duplicates, preserving all occurrences in the final sorted list.

Trees contain negative, zero, and positive values

How to Handle:

The comparison and merging process should correctly order all elements including negative and zero values.

Trees are highly unbalanced or skewed

How to Handle:

Inorder traversal should still be efficient, and the merge process should not degrade to quadratic time based on skewness.

Integer overflow during element comparison

How to Handle:

Utilize a safe comparison method that avoids direct subtraction or addition to prevent potential overflow errors.

Solution

Clarifying Questions

When you get asked this question in a real-life environment, it will often be ambiguous (especially at FAANG). Make sure to ask these questions in that case:

What is the range of values that the nodes in the trees can have? Can they be negative, zero, or floating-point numbers?
Can the trees be empty? What should I return if either or both trees are empty?
Are duplicate values allowed within either of the binary search trees, and if so, how should they be handled in the final sorted list?
Do I need to maintain the relative order of elements that come from the same tree in the final sorted list?
Can I modify the given binary search trees, or should I treat them as immutable?

Brute Force Solution

Approach

Here's how the algorithm would work step-by-step:

First, take all the numbers out of the first tree and put them into a list.
Next, do the same thing for the second tree; put all its numbers into another list.
Now, combine the two lists into one big list.
Finally, sort the big list so the numbers are in increasing order.

Code Implementation

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

def getAllElementsBruteForce(root1, root2):
    first_tree_elements = []
    second_tree_elements = []

    def inorderTraversal(root, elements_list):
        if root:
            inorderTraversal(root.left, elements_list)
            elements_list.append(root.val)
            inorderTraversal(root.right, elements_list)

    # Extract elements from the first BST
    inorderTraversal(root1, first_tree_elements)

    # Extract elements from the second BST
    inorderTraversal(root2, second_tree_elements)

    combined_elements = first_tree_elements + second_tree_elements

    # Sorting to combine the elements
    combined_elements.sort()

    return combined_elements

Big(O) Analysis

Time Complexity

Space Complexity

Optimal Solution

Approach

Here's how the algorithm would work step-by-step:

Go through the first binary search tree and create a sorted list of all its numbers. Because it is a search tree, we can do this efficiently.
Do the same thing for the second binary search tree: make another sorted list of its numbers.
Now you have two sorted lists. Merge these two lists together into one big sorted list. The merging process should maintain the sorted order.
The final sorted list contains all the elements from both trees in the correct order.

Code Implementation

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

class Solution:
    def getAllElements(self, root1: TreeNode, root2: TreeNode) -> list[int]:
        first_tree_elements = []
        second_tree_elements = []

        def inorder_traversal(root: TreeNode, element_list: list[int]) -> None:
            if root:
                inorder_traversal(root.left, element_list)
                element_list.append(root.val)
                inorder_traversal(root.right, element_list)

        # Traverse the first tree and store elements in sorted order.
        inorder_traversal(root1, first_tree_elements)

        # Traverse the second tree and store elements in sorted order.
        inorder_traversal(root2, second_tree_elements)

        merged_elements = []
        first_index = 0
        second_index = 0

        # Merge the two sorted lists into a single sorted list.
        while first_index < len(first_tree_elements) and second_index < len(second_tree_elements):
            if first_tree_elements[first_index] <= second_tree_elements[second_index]:
                merged_elements.append(first_tree_elements[first_index])
                first_index += 1
            else:
                merged_elements.append(second_tree_elements[second_index])
                second_index += 1

        # Add any remaining elements from the first list.
        while first_index < len(first_tree_elements):
            merged_elements.append(first_tree_elements[first_index])
            first_index += 1

        # Add any remaining elements from the second list.
        while second_index < len(second_tree_elements):
            merged_elements.append(second_tree_elements[second_index])
            second_index += 1

        return merged_elements

Big(O) Analysis

Time Complexity

Space Complexity

Edge Cases

Case	How to Handle
Both trees are empty (null)	Return an empty list as there are no elements to merge.
One tree is empty (null), the other is not	Return the sorted list of elements from the non-empty tree.
Both trees contain only one node	Merge the two single-element lists into a single sorted list.
One tree is extremely large, the other is small	Ensure the merge algorithm avoids excessive recursion or stack overflow issues and considers iterative merging approaches for scalability.
Trees contain duplicate values	The merging process should correctly handle duplicates, preserving all occurrences in the final sorted list.
Trees contain negative, zero, and positive values	The comparison and merging process should correctly order all elements including negative and zero values.
Trees are highly unbalanced or skewed	Inorder traversal should still be efficient, and the merge process should not degrade to quadratic time based on skewness.
Integer overflow during element comparison	Utilize a safe comparison method that avoids direct subtraction or addition to prevent potential overflow errors.

Both trees are empty (null)

How to Handle:

Return an empty list as there are no elements to merge.

One tree is empty (null), the other is not

How to Handle:

Return the sorted list of elements from the non-empty tree.

Both trees contain only one node

How to Handle:

Merge the two single-element lists into a single sorted list.

One tree is extremely large, the other is small

How to Handle:

Ensure the merge algorithm avoids excessive recursion or stack overflow issues and considers iterative merging approaches for scalability.

Trees contain duplicate values

How to Handle:

The merging process should correctly handle duplicates, preserving all occurrences in the final sorted list.

Trees contain negative, zero, and positive values

How to Handle:

The comparison and merging process should correctly order all elements including negative and zero values.

Trees are highly unbalanced or skewed

How to Handle:

Inorder traversal should still be efficient, and the merge process should not degrade to quadratic time based on skewness.

Integer overflow during element comparison

How to Handle:

Utilize a safe comparison method that avoids direct subtraction or addition to prevent potential overflow errors.