https://app.laicode.io/app/problem/136
In a binary search tree, find the node containing the largest number smaller than the given target number.
If there is no such number, return INT_MIN.
Assumptions:
- The given root is not null.
- There are no duplicate keys in the binary search tree.
Examples
5
/ \
2 11
/ \
6 14
largest number smaller than 1 is Integer.MIN_VALUE(Java) or INT_MIN(c++)
largest number smaller than 10 is 6
largest number smaller than 6 is 5
How is the binary tree represented?
We use the level order traversal sequence with a special symbol "#" denoting the null node.
For Example:
The sequence [1, 2, 3, #, #, 4] represents the following binary tree:
1
/ \
2 3
/
4
Medium
Binary Search Tree
The tree should not be null or empty
There should not be duplicates in the BST
This problem utilizes the classical BST traversal:
- if (root.key > target) ⇒ go left
- if (root.key < target) ⇒ go right
In this problem particularly, we maintain a global solution variable. This variable gets updated only when a node whose key is smaller than the target is met. Because this condition meets case 2, we need to go right. Since everything on the right of the node is larger than it, when we see another node < target in the right subtree of the current node, we can directly update the global solution.
/**
* public class TreeNode {
* public int key;
* public TreeNode left;
* public TreeNode right;
* public TreeNode(int key) {
* this.key = key;
* }
* }
*/
public class Solution {
public int largestSmaller(TreeNode root, int target) {
// Write your solution here
int result = Integer.MIN_VALUE;
while (root != null) {
if (root.key < target) {
// Case 1: update the result
result = root.key;
root = root.right;
} else {
// Case 2: look for a smaller node
root = root.left;
}
}
return result;
}
}
Time:
On average, if the BST is balanced, traversal of the tree to a leaf node costs O(log(n)). In the worst case where the BST is flattened to a linked list, it is O(n). In either case, the complexity is O(height of the tree)
Space:
No additional data structures used ⇒ O(1)