1305. All Elements in Two Binary Search Trees

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^5<=Node.val<=10^5$

From: LeetCode
Link: 1305. All Elements in Two Binary Search Trees

---

Solution:

Ideas:

Perform inorder traversal on both BSTs to obtain two sorted arrays, then merge them like merge sort.

Code:

#include <stdlib.h>

/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     struct TreeNode *left;
 *     struct TreeNode *right;
 * };
 */

static int countNodes(struct TreeNode* root) {
    if (root == NULL) {
        return 0;
    }

    return 1 + countNodes(root->left) + countNodes(root->right);
}

static void inorder(struct TreeNode* root, int* values, int* index) {
    if (root == NULL) {
        return;
    }

    inorder(root->left, values, index);
    values[(*index)++] = root->val;
    inorder(root->right, values, index);
}

/**
 * Note: The returned array must be malloced, assume caller calls free().
 */
int* getAllElements(struct TreeNode* root1, struct TreeNode* root2,
                    int* returnSize) {
    int size1 = countNodes(root1);
    int size2 = countNodes(root2);
    int totalSize = size1 + size2;

    int* values1 = size1 > 0 ? malloc(size1 * sizeof(int)) : NULL;
    int* values2 = size2 > 0 ? malloc(size2 * sizeof(int)) : NULL;
    int* result = malloc((totalSize > 0 ? totalSize : 1) * sizeof(int));

    int index1 = 0;
    int index2 = 0;

    inorder(root1, values1, &index1);
    inorder(root2, values2, &index2);

    int i = 0;
    int j = 0;
    int k = 0;

    while (i < size1 && j < size2) {
        if (values1[i] <= values2[j]) {
            result[k++] = values1[i++];
        } else {
            result[k++] = values2[j++];
        }
    }

    while (i < size1) {
        result[k++] = values1[i++];
    }

    while (j < size2) {
        result[k++] = values2[j++];
    }

    free(values1);
    free(values2);

    *returnSize = totalSize;
    return result;
}