Problem#
Given a preorder traversal of a Binary Search Tree (BST), determine the number of elements in the traversal that are less than the root node.
Examples#
Example 1#
1
2
3
|
Input: [10, 5, 1, 7, 40, 50]
Output: 3
Explanation: The root is 10. Elements less than 10 are [5, 1, 7].
|
Example 2#
1
2
3
|
Input: [25, 15, 10, 20, 30, 35, 40]
Output: 3
Explanation: The root is 25. Elements less than 25 are [15, 10, 20].
|
Solution#
Method 1 - Naive#
A Binary Search Tree (BST) is structured such that:
- For any node in the tree, all elements in the left subtree are smaller than the node, and all elements in the right subtree are larger than the node.
From the preorder traversal, the first element is always the root. We need to count the elements in the traversal that are less than this root.
Approach#
- Step 1: Extract the root node as the first element of the preorder list.
- Step 2: Iterate through the list and count the elements smaller than the root node.
- Output: Return the count of these smaller elements.
Code#
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
|
class Solution {
public int countElementsLessThanRoot(List<Integer> preorder) {
// Step 1: Extract the root
int root = preorder.get(0);
// Step 2: Count elements less than root
int count = 0;
for (int i = 1; i < preorder.size(); i++) {
if (preorder.get(i) < root) {
count++;
}
}
return count;
}
public static void main(String[] args) {
Solution sol = new Solution();
// Example 1
List<Integer> example1 = List.of(10, 5, 1, 7, 40, 50);
System.out.println(sol.countElementsLessThanRoot(example1)); // Output: 3
// Example 2
List<Integer> example2 = List.of(25, 15, 10, 20, 30, 35, 40);
System.out.println(sol.countElementsLessThanRoot(example2)); // Output: 3
// Example 3
List<Integer> example3 = List.of(40, 30, 20, 35, 50, 60);
System.out.println(sol.countElementsLessThanRoot(example3)); // Output: 4
}
}
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
|
class Solution:
def count_elements_less_than_root(self, preorder):
# Step 1: Extract the root
root = preorder[0]
# Step 2: Count elements less than root
count = sum(1 for x in preorder[1:] if x < root)
return count
# Testing the solution
if __name__ == "__main__":
solution = Solution()
# Example 1
example1 = [10, 5, 1, 7, 40, 50]
print(solution.count_elements_less_than_root(example1)) # Output: 3
# Example 2
example2 = [25, 15, 10, 20, 30, 35, 40]
print(solution.count_elements_less_than_root(example2)) # Output: 3
# Example 3
example3 = [40, 30, 20, 35, 50, 60]
print(solution.count_elements_less_than_root(example3)) # Output: 4
|
Complexity#
- ⏰ Time complexity:
O(n), as we iterate through the preorder traversal once to count elements less than the root.
- 🧺 Space complexity:
O(1). No additional data structures are used apart from the input list (in-place computation).
Method 2 - Using Binary search#
The idea is to employ a modified form of binary search. The steps involve checking the middle element:
- If it is greater than the root, search the left half of the sorted array.
- If it is less than the root and the next element is greater, the middle index gives the count of elements less than the root.
- Otherwise, search the right half.
Code#
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
|
class Solution {
public int countElementsLessThanRoot(int[] preorder) {
// Step 1: Extract the root
int root = preorder[0];
// Step 2: Binary search using BST preorder property
int low = 0, high = preorder.length - 1;
while (low < high) {
int mid = (low + high) / 2;
// If the mid element is greater than the root, move left
if (preorder[mid] > root) {
high = mid - 1;
} else {
// If mid element is smaller, move right
if (mid + 1 < preorder.length && preorder[mid + 1] > root) {
return mid + 1;
}
low = mid + 1;
}
}
return low; // If no elements are smaller than root
}
public static void main(String[] args) {
Solution sol = new Solution();
// Example 1
int[] example1 = {10, 5, 1, 7, 40, 50};
System.out.println(sol.countElementsLessThanRoot(example1)); // Output: 3
// Example 2
int[] example2 = {25, 15, 10, 20, 30, 35, 40};
System.out.println(sol.countElementsLessThanRoot(example2)); // Output: 3
// Example 3
int[] example3 = {40, 30, 20, 35, 50, 60};
System.out.println(sol.countElementsLessThanRoot(example3)); // Output: 4
}
}
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
|
class Solution:
def countElementsLessThanRoot(self, preorder: list[int]) -> int:
# Step 1: Extract the root
root: int = preorder[0]
# Step 2: Binary search using BST preorder property
low: int = 0
high: int = len(preorder) - 1
while low < high:
mid: int = (low + high) // 2
# If the mid element is greater than the root, move left
if preorder[mid] > root:
high = mid - 1
else:
# If mid element is smaller, move right
if mid + 1 < len(preorder) and preorder[mid + 1] > root:
return mid + 1
low = mid + 1
return low # If no elements are smaller than root
# Testing the solution
if __name__ == "__main__":
solution = Solution()
# Example 1
example1: list[int] = [10, 5, 1, 7, 40, 50]
print(solution.countElementsLessThanRoot(example1)) # Output: 3
# Example 2
example2: list[int] = [25, 15, 10, 20, 30, 35, 40]
print(solution.countElementsLessThanRoot(example2)) # Output: 3
# Example 3
example3: list[int] = [40, 30, 20, 35, 50, 60]
print(solution.countElementsLessThanRoot(example3)) # Output: 4
|
Complexity#
- ⏰ Time complexity:
O(log n) due to binary search approach
- 🧺 Space complexity:
O(1)