Builds on Top-Down DFS, which you haven’t finished yet.
BST Property / Range Validation
(low, high), and the BST rule picks the single branch to follow.You're handed the root of a binary tree and must judge whether it is a legitimate binary search tree (BST).
A tree only counts as a valid BST when, at every node:
- everything in its left subtree is strictly smaller than the node's own key,
- everything in its right subtree is strictly larger than the node's own key, and
- both of those subtrees are themselves valid BSTs.
1 sits left of 2 and is smaller; 3 sits right of 2 and is larger.BST Bounds
Root ➔ Validate (low, high) Bounds ➔ Deterministic Branch Selection| 1 | from typing import Optional |
| 2 | |
| 3 | class TreeNode: |
| 4 | def __init__(self, val: int = 0, left: Optional["TreeNode"] = None, right: Optional["TreeNode"] = None): |
| 5 | self.val = val |
| 6 | self.left = left |
| 7 | self.right = right |
| 8 | |
| 9 | def is_valid_bst(root: Optional[TreeNode]) -> bool: |
| 10 | """Validate BST: every node must sit strictly inside the (low, high) window from its |
| 11 | ancestors. |
| 12 | Time: O(N) | Space: O(H) recursion stack |
| 13 | """ |
| 14 | def validate(node: Optional[TreeNode], low: float, high: float) -> bool: |
| 15 | if not node: |
| 16 | return True # Empty subtree is a valid BST |
| 17 | if not (low < node.val < high): |
| 18 | return False # Breaks a bound set by some ancestor, not just the parent |
| 19 | |
| 20 | # Left subtree: cap the high bound; right subtree: raise the low bound |
| 21 | return validate(node.left, low, node.val) and validate(node.right, node.val, high) |
| 22 | |
| 23 | return validate(root, float('-inf'), float('inf')) |
validate accepts satisfies low < node.val < high, where low and high are the tightest bounds set by all its ancestors.A BST node must fit between bounds set by all its ancestors, not just its parent, so carry the window (low, high) down: going left caps high = node.val, going right raises low = node.val, and each node only checks low < node.val < high, starting from -inf and inf, with a strict comparison so duplicate values fail. Searching, inserting, or looking for the closest or next value walks the same window down one path: the target falls on one side of node.val, so one bound tightens and the other subtree is never visited, and when the walk falls off the tree, low and high are the closest values below and above the target. The trap is checking each node only against its children, left.val < node.val < right.val: in [5, 4, 6, null, null, 3, 7] every parent and child pair passes, but the 3 sits in the root's right subtree and breaks the root's rule.
See it run
Validate a BST with a (low, high) window, step by step
node nonelow -high -valid not known yet
Each circle is a tree node. The calls row shows each active call as the node value and its (low, high) window, with the newest call last.
checkingthe node whose value is compared with low and highaccepteda node that passed its windowrejecteda node outside its windowtightensthe edge just followed: it sets a new low or a new high for the child
Call validate on the root 5 with low = -inf and high = inf. No ancestor limits it yet.
Gotcha 1 of 4
- The trap
Gotcha 1: Checking only
left.val < node.val < right.valMistakeif node.left and node.left.val >= node.val: return False if node.right and node.right.val <= node.val: return FalseFixif not (low < node.val < high): return FalseWhat happens: Every node must fit the bounds set by all its ancestors, not only by its parent. In
[5,4,6,null,null,3,7], each parent and child pair is in order. But 3 is in the right subtree of the root 5, so it must be larger than 5.low < node.val < highcarries that bound down from the root.Example: root = [5,4,6,null,null,3,7]Mistake: returns TrueFix: returns False
- You need the values in sorted order or by rank, as in Kth Smallest Element in a BST (LC 230), not a check of each node against bounds from its ancestors. See BST Inorder
Deep Dive
Why the window (low, high) is enough
The rule of a BST (binary search tree) is about whole subtrees. Every value in the left subtree of a node is smaller than that node. Every value in the right subtree is larger. So a node must obey every ancestor, not only its parent.
validate(node, low, high) carries the rule down. When the walk goes left from a node, that node's value is a new upper limit, so high = node.val. When the walk goes right, that value is a new lower limit, so low = node.val. The other limit stays as it was. After many steps, low is the value of the nearest ancestor where the walk went right, and high is the value of the nearest ancestor where the walk went left. These are the tightest limits.
Example: the tree [5, 4, 6, null, null, 3, 7] is not a BST. The calls are (5, -inf, inf), then (4, -inf, 5), then (6, 5, inf), then (3, 5, 6). At the last call, 5 < 3 < 6 is false, so validate returns False. The node 7 is never checked. The and in validate(node.left, ...) and validate(node.right, ...) stops at the first False.
The trap: comparing a node only with its parent
A tempting check is left.val < node.val < right.val at every node. It looks at one level only. On [5, 4, 6, null, null, 3, 7], every parent and child pair is in order: 4 < 5 < 6 and 3 < 6 < 7. A parent-only check returns True. The correct answer is False, because 3 is in the right subtree of 5 and must be larger than 5.
Two smaller traps sit in the same line. The first is <= in place of <. For [2, 2, 2], the strict check returns False, because a left value must be smaller and a right value must be larger. With <= it returns True.
The second is the start of the window. If the root call uses -2**31 and 2**31 - 1, the tree [2147483647] returns False, because the check is strict and the value equals the upper start. Node values in Validate Binary Search Tree (LC 98) can reach both of those numbers. Starting from float('-inf') and float('inf') returns True, which is correct.
The same window finds a place in a BST
When you search for a target, only one child can hold it. If target < node.val, go left and set high = node.val. Otherwise go right and set low = node.val. The other subtree is never visited. This is why Search in a Binary Search Tree (LC 700) and Insert into a Binary Search Tree (LC 701) follow one path.
When the walk falls off the tree, the window is still there. low and high are the closest values below and above the target. Example: in [8, 4, 12, 2, 6, 10, 14], a walk for the target 5 goes through 8, 4 and 6, then falls off the left side of 6. The window is (4, 6). The closest smaller value is 4, and the closest larger value is 6.
Insert into a Binary Search Tree (LC 701) places the new node at the place where the walk fell off. Closest Binary Search Tree Value (LC 270) and Inorder Successor in BST (LC 285) read the window at the end.
The cost, and the neighbour card
Each node is checked once with two comparisons, so the time is O(N). The space is O(H), where H is the height of the tree. The space is the recursion stack. A search or an insert visits one path, so it takes O(H) time.
A very deep tree can exceed the recursion limit. In a test run with Python's default limit, a chain of 900 nodes returned True, and a chain of 1,100 nodes raised RecursionError.
Sorted Walk is the neighbour card. It also uses the BST rule, but it reads the values in sorted order, as in Kth Smallest Element in a BST (LC 230). Use BST Bounds when each node must be checked against the limits of its ancestors, or when one path decides the answer. Use Sorted Walk when the answer depends on the order or the rank of the values.
60-Second Pitch
"A BST node must fit between the limits set by all its ancestors, not only its parent. So I pass a window (low, high) down the tree. The root starts with (-inf, inf). Each node checks low < node.val < high, with a strict comparison. The left child gets (low, node.val). The right child gets (node.val, high). A parent-only check fails on [5, 4, 6, null, null, 3, 7], because 3 is smaller than the root 5 but sits in its right subtree. The window (5, 6) catches it. Each node is visited once, so the time is O(N). The space is O(H) for the recursion. Search and insert use the same window on one path, so they take O(H) time."
Common Questions
- Why not just check that each node is larger than its left child and smaller than its right child?
That checks one level only. In
[5, 4, 6, null, null, 3, 7], every parent and child pair is in order, but 3 is in the right subtree of 5 and is smaller than 5. A node must obey all its ancestors, so the(low, high)window carries their limits down.- Is there another way to validate a BST?
Yes. Walk the tree in order and check that each value is larger than the previous one. For
[2, 2, 2]the second value is not larger, so it returnsFalse. This takesO(N)time and O(H) space as well. The window version also lets you stop early on the first bad node and is easy to reuse for search and insert.- Why start with
float('-inf')andfloat('inf')and not the integer limits? The check is strict. If a node equals the starting limit, it fails. In Validate Binary Search Tree (LC 98), a node can hold
2147483647, sovalidate(root, -231, 231 - 1)returnsFalsefor[2147483647]. Infinity is outside every possible value.- How would you insert a value into a BST with this idea?
Walk down one path. Go left when the value is smaller than
node.val, and go right otherwise. When the walk reaches an empty place, put the new node there. This is Insert into a Binary Search Tree (LC 701). It takes O(H) time, because only one child is visited at each step.- What is the space cost, and when does it become a problem?
O(H) for the recursion stack, where H is the height of the tree. A balanced tree has H about log N. A chain has H = N. In Python, a chain of 1,100 nodes raised
RecursionErrorwith the default limit, so for a very deep tree I would use an explicit stack or an inorder walk with a loop.
SWE Reasoning
Spot it
- The tree is a binary search tree, and the task is to validate it, search it, insert into it, delete from it, trim it or find the closest value.
- The rule "left is smaller, right is larger" must hold for a whole subtree, not only for a child.
- Only one child can hold the target, so one path from the root is enough.
- The wording says "strictly" or says that values are distinct, so the comparison must be strict.
- The answer depends on the limits that the ancestors set, which a single number from a child cannot carry.
The invariant, step by step
validate(root, -inf, inf)starts with no limit, solow = -infandhigh = inf.- A call receives a node and a window. It accepts the node only if
low < node.val < high. - The left child receives
(low, node.val). Every value in the left subtree must be smaller thannode.val, and still larger thanlow. - The right child receives
(node.val, high). Every value in the right subtree must be larger thannode.val, and still smaller thanhigh. - By induction, each node that a call accepts is inside the limits set by all its ancestors, because the window only shrinks as the walk goes down.
- An empty subtree returns
True. The tree is valid when every call returnsTrue.
Traps
- Comparing only with the parent.
[5, 4, 6, null, null, 3, 7]passes every parent and child pair, but 3 is in the right subtree of 5. Carry(low, high)down. <=in the check. A duplicate value passes, so[2, 2, 2]is accepted. Use<.- Starting at
INT_MINandINT_MAX. A node with value2147483647fails the strict check. Start at-infandinf. - Passing the child's value as its own bound.
validate(node.left, low, node.left.val)compares the child with itself. Passnode.val. - Only the left subtree checked. Both calls are needed, joined with
and.
Practice
Builds on Top-Down DFS, which you haven’t finished yet.
BST Property / Range Validation
(low, high), and the BST rule picks the single branch to follow.You're handed the root of a binary tree and must judge whether it is a legitimate binary search tree (BST).
A tree only counts as a valid BST when, at every node:
- everything in its left subtree is strictly smaller than the node's own key,
- everything in its right subtree is strictly larger than the node's own key, and
- both of those subtrees are themselves valid BSTs.
1 sits left of 2 and is smaller; 3 sits right of 2 and is larger.BST Bounds
Root ➔ Validate (low, high) Bounds ➔ Deterministic Branch Selection| 1 | from typing import Optional |
| 2 | |
| 3 | class TreeNode: |
| 4 | def __init__(self, val: int = 0, left: Optional["TreeNode"] = None, right: Optional["TreeNode"] = None): |
| 5 | self.val = val |
| 6 | self.left = left |
| 7 | self.right = right |
| 8 | |
| 9 | def is_valid_bst(root: Optional[TreeNode]) -> bool: |
| 10 | """Validate BST: every node must sit strictly inside the (low, high) window from its |
| 11 | ancestors. |
| 12 | Time: O(N) | Space: O(H) recursion stack |
| 13 | """ |
| 14 | def validate(node: Optional[TreeNode], low: float, high: float) -> bool: |
| 15 | if not node: |
| 16 | return True # Empty subtree is a valid BST |
| 17 | if not (low < node.val < high): |
| 18 | return False # Breaks a bound set by some ancestor, not just the parent |
| 19 | |
| 20 | # Left subtree: cap the high bound; right subtree: raise the low bound |
| 21 | return validate(node.left, low, node.val) and validate(node.right, node.val, high) |
| 22 | |
| 23 | return validate(root, float('-inf'), float('inf')) |
validate accepts satisfies low < node.val < high, where low and high are the tightest bounds set by all its ancestors.A BST node must fit between bounds set by all its ancestors, not just its parent, so carry the window (low, high) down: going left caps high = node.val, going right raises low = node.val, and each node only checks low < node.val < high, starting from -inf and inf, with a strict comparison so duplicate values fail. Searching, inserting, or looking for the closest or next value walks the same window down one path: the target falls on one side of node.val, so one bound tightens and the other subtree is never visited, and when the walk falls off the tree, low and high are the closest values below and above the target. The trap is checking each node only against its children, left.val < node.val < right.val: in [5, 4, 6, null, null, 3, 7] every parent and child pair passes, but the 3 sits in the root's right subtree and breaks the root's rule.
See it run
Validate a BST with a (low, high) window, step by step
node nonelow -high -valid not known yet
Each circle is a tree node. The calls row shows each active call as the node value and its (low, high) window, with the newest call last.
checkingthe node whose value is compared with low and highaccepteda node that passed its windowrejecteda node outside its windowtightensthe edge just followed: it sets a new low or a new high for the child
Call validate on the root 5 with low = -inf and high = inf. No ancestor limits it yet.
Gotcha 1 of 4
- The trap
Gotcha 1: Checking only
left.val < node.val < right.valMistakeif node.left and node.left.val >= node.val: return False if node.right and node.right.val <= node.val: return FalseFixif not (low < node.val < high): return FalseWhat happens: Every node must fit the bounds set by all its ancestors, not only by its parent. In
[5,4,6,null,null,3,7], each parent and child pair is in order. But 3 is in the right subtree of the root 5, so it must be larger than 5.low < node.val < highcarries that bound down from the root.Example: root = [5,4,6,null,null,3,7]Mistake: returns TrueFix: returns False
- You need the values in sorted order or by rank, as in Kth Smallest Element in a BST (LC 230), not a check of each node against bounds from its ancestors. See BST Inorder
Deep Dive
Why the window (low, high) is enough
The rule of a BST (binary search tree) is about whole subtrees. Every value in the left subtree of a node is smaller than that node. Every value in the right subtree is larger. So a node must obey every ancestor, not only its parent.
validate(node, low, high) carries the rule down. When the walk goes left from a node, that node's value is a new upper limit, so high = node.val. When the walk goes right, that value is a new lower limit, so low = node.val. The other limit stays as it was. After many steps, low is the value of the nearest ancestor where the walk went right, and high is the value of the nearest ancestor where the walk went left. These are the tightest limits.
Example: the tree [5, 4, 6, null, null, 3, 7] is not a BST. The calls are (5, -inf, inf), then (4, -inf, 5), then (6, 5, inf), then (3, 5, 6). At the last call, 5 < 3 < 6 is false, so validate returns False. The node 7 is never checked. The and in validate(node.left, ...) and validate(node.right, ...) stops at the first False.
The trap: comparing a node only with its parent
A tempting check is left.val < node.val < right.val at every node. It looks at one level only. On [5, 4, 6, null, null, 3, 7], every parent and child pair is in order: 4 < 5 < 6 and 3 < 6 < 7. A parent-only check returns True. The correct answer is False, because 3 is in the right subtree of 5 and must be larger than 5.
Two smaller traps sit in the same line. The first is <= in place of <. For [2, 2, 2], the strict check returns False, because a left value must be smaller and a right value must be larger. With <= it returns True.
The second is the start of the window. If the root call uses -2**31 and 2**31 - 1, the tree [2147483647] returns False, because the check is strict and the value equals the upper start. Node values in Validate Binary Search Tree (LC 98) can reach both of those numbers. Starting from float('-inf') and float('inf') returns True, which is correct.
The same window finds a place in a BST
When you search for a target, only one child can hold it. If target < node.val, go left and set high = node.val. Otherwise go right and set low = node.val. The other subtree is never visited. This is why Search in a Binary Search Tree (LC 700) and Insert into a Binary Search Tree (LC 701) follow one path.
When the walk falls off the tree, the window is still there. low and high are the closest values below and above the target. Example: in [8, 4, 12, 2, 6, 10, 14], a walk for the target 5 goes through 8, 4 and 6, then falls off the left side of 6. The window is (4, 6). The closest smaller value is 4, and the closest larger value is 6.
Insert into a Binary Search Tree (LC 701) places the new node at the place where the walk fell off. Closest Binary Search Tree Value (LC 270) and Inorder Successor in BST (LC 285) read the window at the end.
The cost, and the neighbour card
Each node is checked once with two comparisons, so the time is O(N). The space is O(H), where H is the height of the tree. The space is the recursion stack. A search or an insert visits one path, so it takes O(H) time.
A very deep tree can exceed the recursion limit. In a test run with Python's default limit, a chain of 900 nodes returned True, and a chain of 1,100 nodes raised RecursionError.
Sorted Walk is the neighbour card. It also uses the BST rule, but it reads the values in sorted order, as in Kth Smallest Element in a BST (LC 230). Use BST Bounds when each node must be checked against the limits of its ancestors, or when one path decides the answer. Use Sorted Walk when the answer depends on the order or the rank of the values.
60-Second Pitch
"A BST node must fit between the limits set by all its ancestors, not only its parent. So I pass a window (low, high) down the tree. The root starts with (-inf, inf). Each node checks low < node.val < high, with a strict comparison. The left child gets (low, node.val). The right child gets (node.val, high). A parent-only check fails on [5, 4, 6, null, null, 3, 7], because 3 is smaller than the root 5 but sits in its right subtree. The window (5, 6) catches it. Each node is visited once, so the time is O(N). The space is O(H) for the recursion. Search and insert use the same window on one path, so they take O(H) time."
Common Questions
- Why not just check that each node is larger than its left child and smaller than its right child?
That checks one level only. In
[5, 4, 6, null, null, 3, 7], every parent and child pair is in order, but 3 is in the right subtree of 5 and is smaller than 5. A node must obey all its ancestors, so the(low, high)window carries their limits down.- Is there another way to validate a BST?
Yes. Walk the tree in order and check that each value is larger than the previous one. For
[2, 2, 2]the second value is not larger, so it returnsFalse. This takesO(N)time and O(H) space as well. The window version also lets you stop early on the first bad node and is easy to reuse for search and insert.- Why start with
float('-inf')andfloat('inf')and not the integer limits? The check is strict. If a node equals the starting limit, it fails. In Validate Binary Search Tree (LC 98), a node can hold
2147483647, sovalidate(root, -231, 231 - 1)returnsFalsefor[2147483647]. Infinity is outside every possible value.- How would you insert a value into a BST with this idea?
Walk down one path. Go left when the value is smaller than
node.val, and go right otherwise. When the walk reaches an empty place, put the new node there. This is Insert into a Binary Search Tree (LC 701). It takes O(H) time, because only one child is visited at each step.- What is the space cost, and when does it become a problem?
O(H) for the recursion stack, where H is the height of the tree. A balanced tree has H about log N. A chain has H = N. In Python, a chain of 1,100 nodes raised
RecursionErrorwith the default limit, so for a very deep tree I would use an explicit stack or an inorder walk with a loop.
SWE Reasoning
Spot it
- The tree is a binary search tree, and the task is to validate it, search it, insert into it, delete from it, trim it or find the closest value.
- The rule "left is smaller, right is larger" must hold for a whole subtree, not only for a child.
- Only one child can hold the target, so one path from the root is enough.
- The wording says "strictly" or says that values are distinct, so the comparison must be strict.
- The answer depends on the limits that the ancestors set, which a single number from a child cannot carry.
The invariant, step by step
validate(root, -inf, inf)starts with no limit, solow = -infandhigh = inf.- A call receives a node and a window. It accepts the node only if
low < node.val < high. - The left child receives
(low, node.val). Every value in the left subtree must be smaller thannode.val, and still larger thanlow. - The right child receives
(node.val, high). Every value in the right subtree must be larger thannode.val, and still smaller thanhigh. - By induction, each node that a call accepts is inside the limits set by all its ancestors, because the window only shrinks as the walk goes down.
- An empty subtree returns
True. The tree is valid when every call returnsTrue.
Traps
- Comparing only with the parent.
[5, 4, 6, null, null, 3, 7]passes every parent and child pair, but 3 is in the right subtree of 5. Carry(low, high)down. <=in the check. A duplicate value passes, so[2, 2, 2]is accepted. Use<.- Starting at
INT_MINandINT_MAX. A node with value2147483647fails the strict check. Start at-infandinf. - Passing the child's value as its own bound.
validate(node.left, low, node.left.val)compares the child with itself. Passnode.val. - Only the left subtree checked. Both calls are needed, joined with
and.