skip to content

In a binary search tree of price levels, how do you find the largest key at or below X when X is absent?

level: seniorimportance: should knowfreq 45%

answer

  1. A missing key need not end the search
  2. Carry one variable down the descent
  3. Only one branch yields a candidate
  4. Which step direction means 'this node qualifies'
  5. The answer is the last right-going step

basics

~20 s

Carry a candidate down the ordinary search descent: when the current key is below X, record it and step right; when it is above X, step left. The last recorded key is the largest at or below X.

solid answer

~50 s

A floor query does not fail on a missing key — it turns the failed search into an answer. Descend from the root carrying a `best` variable. If the current key equals X you are done; if it exceeds X, that node and its whole right subtree are too large, so step left and record nothing; if it is below X, that node is a legal answer, so set `best` to it and step right for something closer. `best` therefore always holds the largest key seen that does not exceed X, and when the descent falls off the bottom it is the answer — or empty, if X is below every key. The trap is returning the parent of the empty slot the search reached; that node may be above X. The answer is the last node where you stepped **right**. Ceiling mirrors it, and both cost `O(h)`.

code

pseudocode · 13 lines
pseudocode
// largest key <= x, or NONE if every key exceeds x
floor(root, x):
  best = NONE
  node = root
  while node != NIL:
    if node.key == x:
      return node.key
    if node.key > x:
      node = node.left          // node and its right subtree are all too large
    else:
      best = node.key           // legal answer; look for a closer one
      node = node.right
  return best

go deeper

for a junior

Know that an ordered tree can answer 'nearest key at or below X' and that this is different from an exact-match lookup, which simply reports absence.

for a middle

Explain the descent: which comparison result makes the current node a candidate, which direction you step afterwards, and why the whole thing costs the same as an ordinary lookup.

for a senior

State the invariant the candidate variable maintains and identify the classic bug of returning the last visited node instead of the last right-going one. Name the edge cases the interface must settle: no floor exists, and inclusive versus strict comparison.

for a principal

Own the query surface: if the dominant workload is nearest-level lookups over a price ladder, the structure must expose floor and ceiling as first-class operations with defined absent-result semantics, rather than leaving callers to build them out of iteration.

## The query, and why it is not just a lookup A **floor** query asks for the largest stored key that is less than or equal to a probe value `X`; **ceiling** asks for the smallest stored key greater than or equal to `X`. This is the query that makes an ordered tree worth its pointers: it answers *nearest key* questions, which a structure that only supports exact-match lookup cannot answer at all without scanning. The concrete setting to keep in mind is an in-memory order book keyed by price level, where each node holds the resting orders at one price. "Give me the best bid at or below 103" is a floor query, and the whole point is that 103 itself is usually not a live price level. An exact-match lookup returns nothing and tells you nothing about what is nearby; the floor descent turns the same walk into a useful answer. ## The descent, and the invariant it maintains Run the ordinary comparison descent, but carry one extra variable: - `node.key == X` → exact hit, return it. - `node.key > X` → this node is too large, and so is everything in its right subtree. Step **left**. Record nothing. - `node.key < X` → this node is a legal answer, and it is the best one seen so far: every previously recorded candidate is an ancestor you left by stepping right, so this node's key is larger than all of them while still not exceeding `X`. Overwrite `best` and step **right**, hunting for something closer still to `X`. The invariant is worth being able to state cleanly: *`best` always holds the largest key encountered so far that does not exceed `X`, and every key not yet examined that could beat it lies inside the current subtree.* When the current subtree becomes empty, there is nothing left that could beat `best`, so `best` is the answer. If the descent never once stepped right, `best` is empty and the correct answer is "no floor exists" — `X` is below every key in the tree. ## A worked trace Price levels, with the tree shaped like this: ``` 100 / \ 95 110 / \ / \ 92 98 105 120 ``` Query: the largest price level at or below `103`. 1. At `100`: `100 < 103`, so `100` is legal. `best = 100`. Step right. 2. At `110`: `110 > 103`. Too large. Step left. `best` unchanged. 3. At `105`: `105 > 103`. Too large. Step left. `best` unchanged. 4. The left child is empty. Stop. Answer: **100**. This trace is the whole argument against the most attractive wrong answer. The last node visited was `105`, and the empty slot's parent is `105` — but `105` is above the probe and is not the floor. The answer is the last node at which the descent stepped *right*, which was the root. Anyone who returns the final parent will be right whenever the descent ends on a right-going step and wrong whenever it ends on a left-going one, which is exactly the sort of bug that passes a handful of hand-picked test cases. Ceiling is the exact mirror: record the candidate when the current key is **greater** than `X` and step left, otherwise step right and record nothing. ## Cost One comparison per level, one path, no backtracking: `O(h)` time and `O(1)` extra space in the loop form. It is the same cost as an exact lookup — the candidate bookkeeping is a single variable assignment on some of the steps. That is the real headline: nearest-key queries are as cheap as exact-match queries on this structure, which is why an ordered tree is the natural home for a price ladder where "the level nearest to X" is the dominant question. The alternative that people reach for first — walk the keys in order and take the last one not exceeding `X` — is `O(n)` and gets slower as the book gets deeper, while the descent is bounded by the height regardless of how many price levels exist. ## Practical edge cases worth naming out loud - **`X` below every key.** No floor exists. The API has to distinguish "no such key" from a legitimate stored key, and conflating the two with a sentinel value is a real source of production bugs when the sentinel is a plausible price. - **`X` above every key.** The floor is the maximum, and the descent finds it naturally by stepping right the whole way. - **Exact hit.** Return immediately; do not keep descending, or you will spend the rest of the path proving what you already know. - **Strict versus inclusive.** "Strictly below `X`" is a different query from "at or below `X`", and it is one comparison different: treat an exact match as too large and keep stepping left. Getting this wrong in a matching engine means crossing a price you were supposed to stop at. ## What a strong answer sounds like Describe the candidate-carrying descent, state the invariant on `best`, name the last-right-step rule explicitly rather than the last-visited node, give the cost as `O(h)`, and mention the empty-result and inclusive-versus-strict edge cases as things the interface has to settle.

  • Why is the parent of the empty slot where the descent ended not the answer?
    Because that node may be above the probe. The descent ends wherever the path runs out, and its final node is the floor only if the last step was a right step. The correct rule is the last node at which the descent went right, which is exactly what the candidate variable records.
  • How does the ceiling query differ?
    It mirrors every branch. Record the candidate when the current key is greater than or equal to the probe and step left to hunt for something closer; when the key is smaller, step right and record nothing. Same descent, same `O(h)` cost, opposite direction of the candidate rule.
  • What changes if the query is 'strictly below X' rather than 'at or below X'?
    One comparison. An exact match is no longer an acceptable answer, so treat `node.key == X` as too large and step left instead of returning. Everything else is unchanged. In a price-matching context this is the difference between stopping at a level and crossing it, so the interface should name which semantics it offers.
  • How should the query report that no floor exists?
    As an explicit empty result, distinct from any stored key. `X` below every key in the tree is a normal outcome, and encoding it as a sentinel price or a zero invites a caller to treat 'nothing qualifies' as a real level. Make absence a separate outcome the caller must handle.

Walking down a street looking for the last house number at or below 103: you note each qualifying door as you pass it, and when the street ends the answer is the last one you noted, not the door you happen to be standing in front of.

saying these in an interview costs you the question

  • Says a floor query fails when the exact key is absent
  • Returns the parent of the empty slot the descent reached
  • Proposes an in-order scan filtering keys below X
  • Claims the query needs a second pass or backtracking
  • Confuses the floor with the tree's minimum key

context

resolving links…