mediumCodingEntryMidSenior
Given a binary tree, decide whether it is a valid binary search tree.
5 min readUpdated 2026-08-15
Answer
Short answer
Every node must fall inside an open interval inherited from its ancestors, not merely compare correctly against its own two children. Recurse carrying a low and high bound, tightening one of them at each descent, or walk in-order and require the sequence to be strictly increasing.
Was this answer helpful?
Likely follow-ups
- Give me a three-node tree that satisfies every parent-child comparison and is not a BST.
- Your bounds start at the minimum and maximum int. What input breaks that?
- How would the answer change if equal keys were allowed in the right subtree?
- Can you do it in O of 1 extra space, given that recursion costs O of h?
Related questions
- Find the lowest common ancestor of two nodes in a binary tree.mediumAlso on trees and recursion5 min
- A bundle can contain products or other bundles, and the pricing code should not care which it is holding. How would you model that?mediumAlso on invariants and recursion6 min
- Implement a FIFO queue using only two stacks, then tell me what a dequeue costs.mediumAlso on invariants4 min
- Merge a list of overlapping intervals, and justify the key you sorted byeasyAlso on invariants4 min