DSA Tracker

Visualize

Floor in BST

Iterative candidate tracking down one root-to-leaf path

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

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.

Details

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.

Problem:Floor in BSTEasy

Iterative candidate tracking down one root-to-leaf path

step 1 / 12

0
2
3
4
5
6
7
8
9

Call stack

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

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

Every step in words

Show all 12 steps
  1. Floor of 10. Initialize floor = -1 (no candidate found yet) and point node at the root, 6.
  2. node holds 6, which is non-null, so we enter the loop and inspect this node.
  3. Is 6 < 10? Yes — 6 is a valid candidate (everything larger might still fit), so record floor = 6. A tighter candidate can only live to the right.
  4. node <- node.right. The pointer moves to 8, looking for a candidate closer to 10 than 6.
  5. node holds 8, which is non-null, so we enter the loop and inspect this node.
  6. Is 8 < 10? Yes — 8 is a valid candidate (everything larger might still fit), so record floor = 8. A tighter candidate can only live to the right.
  7. node <- node.right. The pointer moves to 9, looking for a candidate closer to 10 than 8.
  8. node holds 9, which is non-null, so we enter the loop and inspect this node.
  9. Is 9 < 10? Yes — 9 is a valid candidate (everything larger might still fit), so record floor = 9. A tighter candidate can only live to the right.
  10. node <- node.right, but 9 has no right child — node becomes null, so the walk ends with floor = 9.
  11. node is null — the walk is over. The loop exits with the best candidate recorded so far.
  12. Return floor = 9. Three comparisons (6 → 8 → 9) walked straight down the right spine, updating the candidate each time a node stayed under 10, and the left subtree (2, 0, 4, 3, 5) was never even visited.

Now solve it yourself

Watching is the first half. The second is writing it without the animation.

Solve Floor in BST in the editorAll BST problemsBack to roadmap