Pattern visualizer

Floor in BST

At any node, one comparison against x settles two things at once. If the node's value is <= x, it is a legal candidate for the floor and the pointer moves right chasing a tighter one; if it exceeds x, it and its whole right subtree are disqualified and the pointer moves left. Tracking the best candidate seen so far turns this into a single root-to-leaf walk instead of a full traversal. Animated on: Given a BST and an integer x, find the floor of x: the largest value in the tree that is <= x, or -1 if none exists. root=[6,2,8,0,4,7,9,null,null,3,5], x=10 -> 9..

Iterative candidate tracking down one root-to-leaf path

time O(h) — O(log n) balanced, O(n) skewedspace O(1)step 1 / 12

Call stack

floorBST(root, 10)floor -> -1node -> t6

line 3

Floor of 10. Initialize floor = -1 (no candidate found yet) and point node at the root, 6.

Pseudocode

1FUNCTION floorBST(root, x):
2  floor <- -1
3  node <- root
4  WHILE node != null:
5    IF node.val = x:
6      RETURN node.val
7    ELSE IF node.val < x:
8      floor <- node.val
9      node <- node.right
10    ELSE:
11      node <- node.left
12  RETURN floor

← / → step · space play · Home restart

Where to practice BST

Practice BST problems All BST problems Back to roadmap