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:
[0, 5000].-105 <= Node.val <= 105This approach leverages the in-order traversal property of Binary Search Trees (BSTs), which yields elements in sorted order. We perform an in-order traversal on both trees to extract elements into separate lists. We then merge these two sorted lists into one sorted list.
The C solution uses two utility functions: inOrder, which performs an in-order traversal of a tree, and merge, which merges two sorted arrays. After gathering all elements from both trees using in-order traversal, the resulting arrays are merged to form a single sorted array, which is returned.
C++
Java
Python
C#
JavaScript
Time Complexity: O(n + m) where n and m are the number of nodes in root1 and root2, respectively. Space Complexity: O(n + m) for storing the elements from both trees.
This approach uses stacks to perform an iterative in-order traversal of both trees simultaneously. We make use of two separate stacks to store the nodes of current branches of the trees. The smallest node from the top of the stacks is chosen and processed to build the result list in sorted order.
The C solution implements iterative in-order traversal using stacks. It pushes nodes from both trees onto separate stacks. By comparing the top nodes' values from both stacks, the smaller is popped and its value is added to the result array. This continues until all nodes are processed. This approach efficiently combines elements just in time by always considering the smallest available node.
C++
Java
Python
C#
JavaScript
Time Complexity: O(n + m) for processing all nodes, where n and m are the numbers of nodes in the two trees. Space Complexity: O(h1 + h2) where h1 and h2 are the heights of the two trees for the stack size.
| Approach | Complexity |
|---|---|
| In-Order Traversal and Merging | Time Complexity: O(n + m) where n and m are the number of nodes in root1 and root2, respectively. Space Complexity: O(n + m) for storing the elements from both trees. |
| Iterative In-Order Traversal with Stacks | Time Complexity: O(n + m) for processing all nodes, where n and m are the numbers of nodes in the two trees. Space Complexity: O(h1 + h2) where h1 and h2 are the heights of the two trees for the stack size. |
All Elements in Two Binary Search Trees | LeetCode 1305 | C++, Java, Python • Knowledge Center • 5,001 views views
Watch 9 more video solutions →Practice All Elements in Two Binary Search Trees with our built-in code editor and test cases.
Practice on FleetCodePractice this problem
Open in Editor