1305. All Elements in Two Binary Search Trees

📝 Problem Details

• Title: 1305. All Elements in Two Binary Search Trees
• **Link:**https://leetcode.com/problems/all-elements-in-two-binary-search-trees/
• Difficulty: Medium
• Tags/Categories: Trees DFS Sorting

💭What Were My Initial Thoughts?

- retrieve all elements from two binary trees
- return them in sorted order

- can conduct a DFS on both trees, appending each visited node to a list
- sort the list and then return it

🤔What Did I Struggle With?

~

💡 Explanation of Solution

same as intuition

⌛ Complexity Analysis

Time Complexity: O(n + m (log (m + n))
- traversal + sorting of list

Space Complexity: O(n + m)
- storage of elements in the trees in a list 

💻 Implementation of Solution

/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode() : val(0), left(nullptr), right(nullptr) {}
 *     TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
 *     TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}
 * };
 */
class Solution {
private:
    void dfs(vector<int>&list, TreeNode* root) {
        if(root == nullptr) return;
 
        dfs(list, root->left);
        dfs(list, root->right);
        list.push_back(root->val);
    }
 
public:
    vector<int> getAllElements(TreeNode* root1, TreeNode* root2) {
        vector<int> res;
        dfs(res, root1);
        dfs(res, root2);
        sort(res.begin(), res.end());
        return res;
    }
};