Problem

Given a binary search tree, find the floor and ceiling of a given integer. The floor is the highest element in the tree less than or equal to an integer, while the ceiling is the lowest element in the tree greater than or equal to an integer.

If either value does not exist, return None.

Examples

Example 1

1
2
3
4
5
6
7
8
9

Input: 
    BST:     10
           /    \
          5      15
         / \    /  \
        2   7  12  20
    target = 6
Output: floor = 5, ceiling = 7
Explanation: 5 is the highest value ≤ 6, and 7 is the lowest value ≥ 6.

Example 2

1
2
3
4
5
6
7
8
9

Input:
    BST:     10
           /    \
          5      15
         / \    /  \
        2   7  12  20
    target = 15
Output: floor = 15, ceiling = 15
Explanation: 15 exists in the tree, so both floor and ceiling are 15.

Example 3

1
2
3
4
5
6
7
8
9

Input:
    BST:     10
           /    \
          5      15
         / \    /  \
        2   7  12  20
    target = 1
Output: floor = None, ceiling = 2
Explanation: No value ≤ 1 exists, but 2 is the smallest value ≥ 1.

Example 4

1
2
3
4
5
6
7
8
9

Input:
    BST:     10
           /    \
          5      15
         / \    /  \
        2   7  12  20
    target = 25
Output: floor = 20, ceiling = None
Explanation: 20 is the highest value ≤ 25, but no value ≥ 25 exists.

Example 5

1
2
3
4
5

Input:
    BST: empty tree
    target = 10
Output: floor = None, ceiling = None
Explanation: Empty tree has no floor or ceiling values.

Solution

Method 1 - Iterative BST Traversal

Intuition

We can use the BST property to efficiently find floor and ceiling. For each node, if the value equals target, both floor and ceiling are found. If value is less than target, it’s a potential floor candidate and we search right. If value is greater than target, it’s a potential ceiling candidate and we search left.

Approach

  1. Initialize floor and ceiling as None
  2. Start from root and traverse the BST
  3. At each node:
    • If node value equals target: both floor and ceiling are found
    • If node value < target: update floor candidate and go right
    • If node value > target: update ceiling candidate and go left
  4. Continue until we reach a leaf or find exact match
  5. Return the final floor and ceiling values

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

struct TreeNode {
    int val;
    TreeNode* left;
    TreeNode* right;
    TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
};

class Solution {
public:
    pair<int*, int*> floorCeiling(TreeNode* root, int target) {
        int* floor = nullptr;
        int* ceiling = nullptr;
        
        TreeNode* curr = root;
        while (curr) {
            if (curr->val == target) {
                floor = new int(curr->val);
                ceiling = new int(curr->val);
                break;
            } else if (curr->val < target) {
                floor = new int(curr->val);
                curr = curr->right;
            } else {
                ceiling = new int(curr->val);
                curr = curr->left;
            }
        }
        
        return {floor, ceiling};
    }
};
 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

type TreeNode struct {
    Val   int
    Left  *TreeNode
    Right *TreeNode
}

func floorCeiling(root *TreeNode, target int) (*int, *int) {
    var floor, ceiling *int
    
    curr := root
    for curr != nil {
        if curr.Val == target {
            val := curr.Val
            floor = &val
            ceiling = &val
            break
        } else if curr.Val < target {
            val := curr.Val
            floor = &val
            curr = curr.Right
        } else {
            val := curr.Val
            ceiling = &val
            curr = curr.Left
        }
    }
    
    return floor, ceiling
}
 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 TreeNode {
    int val;
    TreeNode left;
    TreeNode right;
    TreeNode(int val) { this.val = val; }
}

class Solution {
    public int[] floorCeiling(TreeNode root, int target) {
        Integer floor = null;
        Integer ceiling = null;
        
        TreeNode curr = root;
        while (curr != null) {
            if (curr.val == target) {
                floor = curr.val;
                ceiling = curr.val;
                break;
            } else if (curr.val < target) {
                floor = curr.val;
                curr = curr.right;
            } else {
                ceiling = curr.val;
                curr = curr.left;
            }
        }
        
        return new int[] {
            floor != null ? floor : -1,
            ceiling != null ? ceiling : -1
        };
    }
}
 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 TreeNode:
    def __init__(self, val: int = 0, left: 'TreeNode' = None, right: 'TreeNode' = None):
        self.val = val
        self.left = left
        self.right = right

class Solution:
    def floorCeiling(self, root: TreeNode, target: int) -> tuple[int, int]:
        floor = None
        ceiling = None
        
        curr = root
        while curr:
            if curr.val == target:
                floor = curr.val
                ceiling = curr.val
                break
            elif curr.val < target:
                floor = curr.val
                curr = curr.right
            else:
                ceiling = curr.val
                curr = curr.left
        
        return (floor, ceiling)

Complexity

  • ⏰ Time complexity: O(h), where h is the height of the BST (O(log n) for balanced, O(n) for skewed)
  • 🧺 Space complexity: O(1), only using constant extra space for variables

Method 2 - Recursive BST Traversal

Intuition

We can solve this recursively by exploring both directions of the BST. For floor, we keep track of the best candidate less than or equal to target. For ceiling, we track the best candidate greater than or equal to target. The recursive approach naturally handles the BST property.

Approach

  1. Create separate recursive functions for finding floor and ceiling
  2. For floor:
    • If current node is null, return None
    • If node value equals target, return it
    • If node value > target, search left subtree
    • If node value < target, this could be floor, but check right subtree for better option
  3. For ceiling:
    • If current node is null, return None
    • If node value equals target, return it
    • If node value < target, search right subtree
    • If node value > target, this could be ceiling, but check left subtree for better option
  4. Combine both results and return

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

class Solution {
private:
    int findFloor(TreeNode* root, int target) {
        if (!root) return -1;
        
        if (root->val == target) return root->val;
        
        if (root->val > target) {
            return findFloor(root->left, target);
        }
        
        int floorVal = findFloor(root->right, target);
        return (floorVal != -1) ? floorVal : root->val;
    }
    
    int findCeiling(TreeNode* root, int target) {
        if (!root) return -1;
        
        if (root->val == target) return root->val;
        
        if (root->val < target) {
            return findCeiling(root->right, target);
        }
        
        int ceilVal = findCeiling(root->left, target);
        return (ceilVal != -1) ? ceilVal : root->val;
    }
    
public:
    pair<int, int> floorCeiling(TreeNode* root, int target) {
        int floor = findFloor(root, target);
        int ceiling = findCeiling(root, target);
        return {floor, ceiling};
    }
};
 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
42
43
44
45
46
47
48
49

func findFloor(root *TreeNode, target int) *int {
    if root == nil {
        return nil
    }
    
    if root.Val == target {
        val := root.Val
        return &val
    }
    
    if root.Val > target {
        return findFloor(root.Left, target)
    }
    
    if floorVal := findFloor(root.Right, target); floorVal != nil {
        return floorVal
    }
    
    val := root.Val
    return &val
}

func findCeiling(root *TreeNode, target int) *int {
    if root == nil {
        return nil
    }
    
    if root.Val == target {
        val := root.Val
        return &val
    }
    
    if root.Val < target {
        return findCeiling(root.Right, target)
    }
    
    if ceilVal := findCeiling(root.Left, target); ceilVal != nil {
        return ceilVal
    }
    
    val := root.Val
    return &val
}

func floorCeilingRecursive(root *TreeNode, target int) (*int, *int) {
    floor := findFloor(root, target)
    ceiling := findCeiling(root, target)
    return floor, ceiling
}
 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 {
    private Integer findFloor(TreeNode root, int target) {
        if (root == null) return null;
        
        if (root.val == target) return root.val;
        
        if (root.val > target) {
            return findFloor(root.left, target);
        }
        
        Integer floorVal = findFloor(root.right, target);
        return floorVal != null ? floorVal : root.val;
    }
    
    private Integer findCeiling(TreeNode root, int target) {
        if (root == null) return null;
        
        if (root.val == target) return root.val;
        
        if (root.val < target) {
            return findCeiling(root.right, target);
        }
        
        Integer ceilVal = findCeiling(root.left, target);
        return ceilVal != null ? ceilVal : root.val;
    }
    
    public int[] floorCeilingRecursive(TreeNode root, int target) {
        Integer floor = findFloor(root, target);
        Integer ceiling = findCeiling(root, target);
        
        return new int[] {
            floor != null ? floor : -1,
            ceiling != null ? ceiling : -1
        };
    }
}
 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

class Solution:
    def _findFloor(self, root: TreeNode, target: int) -> int:
        if not root:
            return None
        
        if root.val == target:
            return root.val
        
        if root.val > target:
            return self._findFloor(root.left, target)
        
        floor_val = self._findFloor(root.right, target)
        return floor_val if floor_val is not None else root.val
    
    def _findCeiling(self, root: TreeNode, target: int) -> int:
        if not root:
            return None
        
        if root.val == target:
            return root.val
        
        if root.val < target:
            return self._findCeiling(root.right, target)
        
        ceil_val = self._findCeiling(root.left, target)
        return ceil_val if ceil_val is not None else root.val
    
    def floorCeilingRecursive(self, root: TreeNode, target: int) -> tuple[int, int]:
        floor = self._findFloor(root, target)
        ceiling = self._findCeiling(root, target)
        return (floor, ceiling)

Complexity

  • ⏰ Time complexity: O(h), where h is the height of the BST, visiting each node at most once
  • 🧺 Space complexity: O(h), recursion stack depth equals the height of the tree