Leetcode 1305. All Elements in Two Binary Search Trees

Problem Explanation

In this problem, two Binary Search Trees (BSTs) are given. A Binary Search Tree is a tree data structure where each node has at most two children, referred to as the left child and the right child. The key property of a Binary Search Tree is that the value of a node is larger than or equal to the values in the nodes of its left sub-tree and smaller than the values in the nodes of its right sub-tree.

The problem then asks to return a sorted list of integers from both the BSTs in ascending order.

For example, consider the BSTs root1 = [2,1,4] and root2 = [1,0,3]. The sorted list containing all elements of two BSTs would be [0,1,1,2,3,4].

Solution Approach

The idea is to traverse both the BSTs using two iterators and push the elements into a container, while making sure that they're sorted in ascending order.

We start by initializing two stack data structures for both the BST. A BSTIterator class is then used to push all left nodes till we reach the end in both the BST. After which, we peek into both the iterators. If the top of the first iterator is smaller, we pop it and move to the next node in the BST. Similarly, if the second iterator's top is smaller, we pop it and move to the next node. This is continued until we exhaust all nodes in both the BSTs. The resultant collection of these popped out elements from the two BSTs forms the sorted list of all elements.

Python Solution

1
2python
3class BSTIterator:
4    def __init__(self, root):
5        self.stack = []
6        self._leftmost_inorder(root)
7
8    def _leftmost_inorder(self, root):
9        while root:
10            self.stack.append(root)
11            root = root.left
12
13    def pop(self):
14        if not self.stack:
15            return None
16        node = self.stack.pop()
17        if node.right:
18            self._leftmost_inorder(node.right)
19        return node.val
20
21    def hasNext(self):
22        return len(self.stack) > 0
23
24class Solution:
25    def getAllElements(self, root1, root2):
26        iter1, iter2 = BSTIterator(root1), BSTIterator(root2)
27        res, node1, node2 = [], iter1.pop(), iter2.pop()
28        while node1 is not None or node2 is not None:
29            if node2 is None or node1 is not None and node1 <= node2:
30                res.append(node1)
31                node1 = iter1.pop()
32            else:
33                res.append(node2)
34                node2 = iter2.pop()
35        return res

Java Solution

1
2java
3class BSTIterator {
4    private Stack<TreeNode> stack;
5
6    public BSTIterator(TreeNode root) {
7        this.stack = new Stack<TreeNode>();
8        this._leftmostInorder(root);
9    }
10
11    private void _leftmostInorder(TreeNode root) {
12        while (root != null) {
13            this.stack.push(root);
14            root = root.left;
15        }
16    }
17
18    public int pop() {
19        TreeNode topmostNode = this.stack.pop();
20        if (topmostNode.right != null) {
21            this._leftmostInorder(topmostNode.right);
22        }
23
24        return topmostNode.val;
25    }
26
27    public boolean hasNext() {
28        return this.stack.size() > 0;
29    }
30}
31
32class Solution {
33    public List<Integer> getAllElements(TreeNode root1, TreeNode root2) {
34
35        List<Integer> result = new ArrayList<Integer>();
36        BSTIterator iterator1 = new BSTIterator(root1);
37        BSTIterator iterator2 = new BSTIterator(root2);
38
39        Integer value1, value2;
40        value1 = iterator1.hasNext() ? iterator1.pop() : null;
41        value2 = iterator2.hasNext() ? iterator2.pop() : null;
42
43        while (value1 != null || value2 != null) {
44            if (value1 != null && value2 != null) {
45                if (value1 <= value2) {
46                    result.add(value1);
47                    value1 = iterator1.hasNext() ? iterator1.pop() : null;
48                } else {
49                    result.add(value2);
50                    value2 = iterator2.hasNext() ? iterator2.pop() : null;
51                }
52            } else if (value2 != null) {
53                result.add(value2);
54                value2 = iterator2.hasNext() ? iterator2.pop() : null;
55            } else {
56                result.add(value1);
57                value1 = iterator1.hasNext() ? iterator1.pop() : null;
58            }
59        }
60
61        return result;
62    }
63}

JavaScript Solution

1
2javascript
3class BSTIterator {
4    constructor(root) {
5        this.stack = [];
6        this.pushLeft(root);
7    }
8   
9    pushLeft(node) {
10        while (node) {
11            this.stack.push(node);
12            node = node.left;
13        }
14    }
15   
16    hasNext() {
17        return this.stack.length > 0;
18    }
19   
20    next() {
21        const topNode = this.stack.pop();
22        if (topNode.right) {
23            this.pushLeft(topNode.right);
24        }
25           
26        return topNode.val;
27    }
28   
29    peek() {
30        return this.stack[this.stack.length - 1].val;
31    }
32}
33   
34var getAllElements = function(root1, root2) {
35    const iter1 = new BSTIterator(root1);
36    const iter2 = new BSTIterator(root2);
37    const output = [];
38        
39    while(iter1.hasNext() || iter2.hasNext()) {
40        let val1, val2;
41            
42        if(iter1.hasNext()) {
43            val1 = iter1.peek();
44        }
45            
46        if(iter2.hasNext()) {
47            val2 = iter2.peek();
48        }
49            
50        if(val1 !== undefined && val2 !== undefined) {
51            if(val1 < val2) {
52                output.push(iter1.next());
53            } else {
54                output.push(iter2.next());
55            }
56        } else if(!iter1.hasNext()) {
57            output.push(iter2.next());
58        } else {
59            output.push(iter1.next());
60        }
61    }
62        
63    return output;
64};

C++ Solution

1
2cpp
3class BSTIterator {
4public:
5    stack<TreeNode*> stack;
6    
7    void leftmostInorder(TreeNode* root) {
8        while (root != NULL) {
9            stack.push(root);
10            root = root->left;
11        }
12    }
13    
14    BSTIterator(TreeNode* root) {
15        leftmostInorder(root);
16    }
17    
18    int next() {
19        TreeNode* topNode = stack.top();
20        stack.pop();
21        
22        if (topNode->right != NULL) {
23            leftmostInorder(topNode->right);
24        }
25        
26        return topNode->val;
27    }
28    
29    bool hasNext() {
30        return stack.size() > 0;
31    }
32};
33
34class Solution {
35public:
36    vector<int> getAllElements(TreeNode* root1, TreeNode* root2) {
37        BSTIterator iterator1 = BSTIterator(root1), iterator2 = BSTIterator(root2);
38        vector<int> result;
39        
40        while (iterator1.hasNext() || iterator2.hasNext()) {
41            int val1, val2;
42            
43            if (iterator1.hasNext()) {
44                val1 = iterator1.stack.top()->val;
45            }
46            
47            if (iterator2.hasNext()) {
48                val2 = iterator2.stack.top()->val;
49            }
50            
51            if (!iterator1.hasNext()) {
52                result.push_back(iterator2.next());
53            } else if (!iterator2.hasNext()) {
54                result.push_back(iterator1.next());
55            } else if (val1 < val2) {
56                result.push_back(iterator1.next());
57            } else {
58                result.push_back(iterator2.next());
59            }
60        }
61        
62        return result;
63    }
64};

C# Solution

1
2csharp
3public class BSTIterator {
4    private Stack<TreeNode> stack = new Stack<TreeNode>();
5    
6    public BSTIterator(TreeNode root) {
7        this.leftmostInorder(root);
8    }
9
10    private void leftmostInorder(TreeNode root) {
11        while (root != null) {
12            this.stack.Push(root);
13            root = root.left;
14        }   
15    }
16
17    public int Pop() {
18        TreeNode topmostNode = this.stack.Pop();
19
20        if (topmostNode.right != null) {
21            this.leftmostInorder(topmostNode.right);
22        }
23
24        return topmostNode.val;
25    }
26
27    public bool HasNext() {
28        return this.stack.Count > 0;
29    }
30}
31
32public class Solution {
33    public IList<int> GetAllElements(TreeNode root1, TreeNode root2) {
34
35        List<int> result = new List<int>();
36        BSTIterator itr1 = new BSTIterator(root1);
37        BSTIterator itr2 = new BSTIterator(root2);
38
39        while (itr1.HasNext() || itr2.HasNext()) {
40            if (!itr1.HasNext()) {
41                result.Add(itr2.Pop());
42            }
43            else if (!itr2.HasNext()) {
44                result.Add(itr1.Pop());
45            }
46            else if (itr1.stack.Peek().val < itr2.stack.Peek().val) {
47                result.Add(itr1.Pop());
48            } else {
49                result.Add(itr2.Pop());
50            }
51        }
52
53        return result;
54    }
55}

Here for all programming languages, we create a BSTIterator class that helps in traversing the binary search tree in inorder fashion. After that, check for both iterators if they have a next node. If there is then the node is popped and added to the result. If one iterator expires, we continue the process with the other one. Repeat the process while nodes exist in both BSTs. In this way, we get the resultant array in sorted fashion. As the binary trees are BSTs, the elements in each binary tree are in sorted order. Merging them will give the resultant array in sorted order.## Time and Space Complexity

The time complexity of this solution is O(N), where N is the total number of nodes in both BSTs. This is because we are traversing all the nodes in both trees once.

The space complexity is O(H1+H2), where H1 and H2 are the heights of the two BSTs. This is because at most, the iterator will hold all the nodes of one branch of the BST. In the worst case (a skew BST), this branch represents the height of the tree.

Therefore, this solution is efficient in terms of both time and space complexity since we are utilizing the properties of the Binary Search Tree (BST) to solve the problem.

Applying this approach in Python, Java, JavaScript, C++ and C# we've shown that we can effectively address such problems. Remember that it is always good practice to consider the characteristics of your data (in this case, the properties of BSTs) when designing your solution. This can often lead to more efficient algorithms and cleaner code.

In conclusion, this problem provides a good exercise in understanding and manipulating tree data structures, particularly Binary Search Trees. The solutions shown here can form a basis for tackling related problems and applying these concepts in different contexts. As always, the key to successful problem-solving in programming lies in logical thinking, understanding your data, and familiarity with your tools and language of choice.


Got a question? Ask the Teaching Assistant anything you don't understand.

Still not clear? Ask in the Forum,  Discord or Submit the part you don't understand to our editors.


TA 👨‍🏫