All Elements in Two Binary Search Trees - Practice Coding Problems

All Elements in Two Binary Search Trees - Problem

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

A binary search tree (BST) is a tree where for every node, all values in the left subtree are smaller and all values in the right subtree are larger than the node's value.

Constraints:

The number of nodes in each tree is in the range [0, 5000]
-10⁵ ≤ Node.val ≤ 10⁵

Input & Output

Example 1 — Basic Two BSTs

$ Input: root1 = [2,1,4], root2 = [1,0,3]

› Output: [0,1,1,2,3,4]

💡 Note: BST1 inorder: [1,2,4], BST2 inorder: [0,1,3]. Merged result: [0,1,1,2,3,4]

Example 2 — One Empty Tree

$ Input: root1 = [5,1,7], root2 = []

› Output: [1,5,7]

💡 Note: BST1 inorder: [1,5,7], BST2 is empty. Result is just BST1's values in sorted order.

Example 3 — Single Node Trees

$ Input: root1 = [1], root2 = [8]

› Output: [1,8]

💡 Note: BST1 has [1], BST2 has [8]. Combined sorted: [1,8]

Constraints

The number of nodes in each tree is in the range [0, 5000]
-10⁵ ≤ Node.val ≤ 10⁵

Visualization

Tap to expand

Understanding the Visualization

Input BSTs

Two binary search trees with sorted property

Extract Values

Get all values maintaining sort order

Merge Result

Combined sorted array with all elements

Key Takeaway

🎯 Key Insight: BST inorder traversal naturally gives sorted order - use this property to avoid unnecessary sorting!

Asked in

A Amazon 38 G Google 25 M Microsoft 20 F Facebook 15

The key insight is leveraging the BST property: inorder traversal gives sorted order. Best approach is inorder traversal + merge - traverse each BST to get sorted arrays, then merge them like merging two sorted lists. Time: O(m+n), Space: O(m+n)

Common Approaches

Approach	Time	Space	Notes
✓ Inorder Traversal + Merge	O(m+n)	O(m+n)	Use inorder traversal to get sorted arrays, then merge them
Collect All and Sort	O((m+n)log(m+n))	O(m+n)	Traverse both trees to collect all values, then sort the combined list

Inorder Traversal + Merge — Algorithm Steps

Inorder traverse first BST to get sorted array
Inorder traverse second BST to get sorted array
Merge two sorted arrays using two pointers

Visualization

Tap to expand

Step-by-Step Walkthrough

Inorder BST1

Get sorted array [1,2,4]

Inorder BST2

Get sorted array [1,3]

Merge Arrays

Two pointers merge to [1,1,2,3,4]

Code -

solution.c — C

#include <stdio.h>
#include <stdlib.h>
#include <string.h>

struct TreeNode {
    int val;
    struct TreeNode* left;
    struct TreeNode* right;
};

void inorder(struct TreeNode* node, int* arr, int* size) {
    if (!node) return;
    inorder(node->left, arr, size);
    arr[(*size)++] = node->val;
    inorder(node->right, arr, size);
}

int* solution(struct TreeNode* root1, struct TreeNode* root2, int* returnSize) {
    int* arr1 = (int*)malloc(5000 * sizeof(int));
    int* arr2 = (int*)malloc(5000 * sizeof(int));
    int size1 = 0, size2 = 0;
    
    inorder(root1, arr1, &size1);
    inorder(root2, arr2, &size2);
    
    int* result = (int*)malloc((size1 + size2) * sizeof(int));
    int i = 0, j = 0, k = 0;
    
    // Merge two sorted arrays
    while (i < size1 && j < size2) {
        if (arr1[i] <= arr2[j]) {
            result[k++] = arr1[i++];
        } else {
            result[k++] = arr2[j++];
        }
    }
    
    while (i < size1) result[k++] = arr1[i++];
    while (j < size2) result[k++] = arr2[j++];
    
    *returnSize = k;
    free(arr1);
    free(arr2);
    return result;
}

int main() {
    int returnSize;
    int* res = solution(NULL, NULL, &returnSize);
    
    printf("[");
    for (int i = 0; i < returnSize; i++) {
        printf("%d", res[i]);
        if (i < returnSize - 1) printf(",");
    }
    printf("]\n");
    
    free(res);
    return 0;
}

Time & Space Complexity

Time Complexity

⏱️

O(m+n)

O(m) to traverse first tree, O(n) to traverse second tree, O(m+n) to merge

✓ Linear Growth

Space Complexity

O(m+n)

Two arrays to store sorted values from both trees

⚡ Linearithmic Space

125.0K Views

Medium Frequency

~18 min Avg. Time

2.1K Likes

Ln 1, Col 1

Smart Actions

💡 Explanation

AI Ready

💡 Suggestion Tab to accept Esc to dismiss

// Output will appear here after running code

Code Editor Closed

Click the red button to reopen

Input & Output

Constraints

Visualization

Related Problems

Common Approaches

Inorder Traversal + Merge — Algorithm Steps

Visualization

Code -

Time & Space Complexity

Select Compiler