Builds on BST Bounds and Tree Traversals, which you haven’t finished yet.
Inorder Traversal as a Sorted Stream (Kth Smallest in BST, BST Iterator)
You get the root of a binary search tree and a whole number k. Imagine writing every value in the tree in a row, smallest first, and numbering the positions from 1: return the value that lands in position k.
In a binary search tree, the values in a node's left subtree are smaller than the node's value, and the values in its right subtree are larger.
Follow-up: if nodes are inserted and deleted often and this question is asked again and again, how would you make each answer faster?
1, 2, 3, 4. Position 1 holds 1, a leaf on the left, even though 3 sits at the top of the tree.BST Inorder
BST ➔ inorder walk (left, node, right) ➔ values in sorted order| 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 kth_smallest(root: Optional[TreeNode], k: int) -> int: |
| 10 | """Kth Smallest Element in a BST: an inorder walk visits the values in sorted order. |
| 11 | Time: O(H + k) | Space: O(H) stack |
| 12 | """ |
| 13 | # Nodes whose left subtree is being walked; each waits for its visit |
| 14 | stack: list[TreeNode] = [] |
| 15 | node = root |
| 16 | while node or stack: |
| 17 | while node: # 1. Dive left: every smaller value sits in a left subtree |
| 18 | stack.append(node) |
| 19 | node = node.left |
| 20 | node = stack.pop() # 2. Visit: the smallest value not visited yet |
| 21 | k -= 1 # Count a node when it is visited, never when it is pushed |
| 22 | if k == 0: |
| 23 | return node.val # The k-th visit is the k-th smallest value |
| 24 | node = node.right # 3. Its right subtree holds the next larger values |
| 25 | return -1 # Never reached: 1 <= k <= n |
stack in ascending order: when stack.pop() returns node, every value smaller than node.val has already been visited, and every node still on stack holds a larger value.An inorder walk of a BST (left subtree, then the node, then the right subtree) visits the values in sorted order, so read the tree as a sorted list, one value per visit: count, compare or collect at the moment stack.pop() hands you a node, and stop as soon as you have the answer. The inner loop pushes node and moves to node.left until it falls off the tree, so when a node is popped, its left subtree has been visited, and so has every ancestor it sits to the right of: those are exactly the smaller values. node = node.right then moves on to the next larger values. The trap is where you count: k -= 1 belongs right after stack.pop(), not next to stack.append(node), because nodes are pushed from the root down, and on [3,1,4,null,2] counting pushes returns 3 for k = 1 instead of 1.
See it run
Inorder walk that stops at the k-th visit, step by step
k 3node 5answer not found yet
Each circle is a tree node. The stack row has its top on the right. The visited row shows the values in the order they were popped.
nodethe node the loop is looking aton stackpushed, and waiting for its left subtree to finishvisitedpopped and countedanswerthe k-th value popped
Start at the root 5 with k = 3. Dive left and push every node on the stack.
Gotcha 1 of 4
- The trap
Gotcha 1: Counting
k -= 1when a node is pushedMistakewhile node: stack.append(node) k -= 1 if k == 0: return node.val node = node.left node = stack.pop()Fixwhile node: stack.append(node) node = node.left node = stack.pop() k -= 1 if k == 0: return node.valWhat happens: A pushed node is only waiting for its visit. The pushes go from the root down, so the root is pushed first. The values come in sorted order only when nodes are popped. In the example, counting pushes stops at the root 3 for
k = 1. The smallest value is 1.Example: Kth Smallest Element in a BST (LC 230): root = [3,1,4,null,2], k = 1Mistake: returns 3Fix: returns 1
- You only need the one place where a value belongs, as in Insert into a Binary Search Tree (LC 701), not the values in order: a single path down from the root decides it. See BST Bounds
- The values arrive one at a time and are not kept in a BST, as in Kth Largest Element in a Stream (LC 703): there is no tree whose inorder walk hands you sorted order. See Top-K Heap
Deep Dive
Why values leave the stack in ascending order
In a BST (binary search tree), a node's left subtree holds smaller values and its right subtree holds larger values. An inorder walk visits the left subtree, then the node, then the right subtree. So a node is visited after all of its smaller values, and before all of its larger values.
The blueprint does this with a stack. The inner loop pushes node and moves to node.left until there is no node. The top of stack is then the smallest value that is not visited yet. stack.pop() visits it. Then node = node.right moves to the next larger values. Every node that stays on stack has not been visited yet, and each one holds a larger value than the node just popped.
Example: in Kth Smallest Element in a BST (LC 230), take root = [5, 3, 6, 2, 4, null, null, 1] and k = 3. The pushes are 5, 3, 2 and 1. The pops are 1, then 2, then 3. After the third pop, k is 0, so the answer is 3. The values came out in the order 1, 2, 3.
The trap: count when a node is popped, not when it is pushed
A node is pushed from the root down, so the first node pushed is the root. The root is not the smallest value. A pushed node is only waiting for its visit. The pop is the visit.
If k -= 1 sits next to stack.append(node), the count follows the pushes. On root = [3, 1, 4, null, 2] with k = 1, the first push is the root 3. The count reaches 0 there, so the function returns 3. The correct answer is 1.
Two more traps are in the loop. The outer condition must be while node or stack. At the start, stack is empty, so while stack never runs and the function returns -1. Also use node = node.right after the pop. If you push node.right onto stack instead, the dive into the left side of that right child is skipped. On [2, 1, 4, null, null, 3] with k = 3, that version returns 4. The correct answer is 3, because 3 is the left child of 4.
Stopping early, and the cost O(H + k)
The walk stops at the k-th visit. It does not read the whole tree. Before the first pop it pushes one node per level on the way to the leftmost node, so that is H pushes, where H is the height of the tree. After that, each pop and each right move is one more visit.
Example: the tree [4, 2, 6, 1, 3, 5, 7] has 7 nodes and height 3. With k = 1 the walk makes 3 pushes and 1 pop. With k = 7 it makes 7 pushes and 7 pops.
Compare this with building a list of all N values and then reading position k - 1. That always costs O(N) time. The stack holds at most H nodes, so the space is O(H). For a chain of 100 nodes that leans to the left, the walk makes 100 pushes before the first pop. That is the worst case for H.
Which problems read the sorted stream, and the neighbour cards
Once the walk gives the values in order, other questions are short. In Minimum Absolute Difference in BST (LC 530) and Minimum Distance Between BST Nodes (LC 783), the smallest gap is always between two values that are next to each other in sorted order. Keep the previous value and compare it with each new value.
In Closest Binary Search Tree Value II (LC 272), keep the last k visited values. When a new value is not closer to the target than the oldest kept value, stop. Every later value is larger and therefore farther.
BST Bounds is the neighbour card. In Insert into a Binary Search Tree (LC 701), one path from the root decides the answer, so you do not need the values in order. In Kth Largest Element in a Stream (LC 703), the values arrive one at a time and are not stored in a tree. There is no tree to walk in order.
60-Second Pitch
"In a BST, an inorder walk visits the values in ascending order. So the k-th visit is the k-th smallest value. I walk with an explicit stack. The inner loop pushes the node and moves left until it falls off the tree. Then I pop, which gives the smallest value not yet visited. I count there, and I return when k reaches 0. Then I move to the right child. I count at the pop and not at the push, because the push goes from the root down and the root is not the smallest. The time is O(H + k), because the first dive pushes H nodes and then each visit is cheap. The space is O(H) for the stack."
Common Questions
- Why does an inorder walk of a BST give sorted values?
The BST rule puts smaller values in the left subtree and larger values in the right subtree. Inorder visits left, then the node, then right. So a node comes after all smaller values and before all larger values. By induction, the whole walk is in ascending order.
- What is the time complexity of the Kth Smallest Element in a BST (LC 230) walk?
O(H + k). The first dive pushes about H nodes, where H is the height of the tree. Then each of the k visits does a small amount of work. The space is O(H) for the stack. A walk that first collects all values costs
O(N).- The tree changes often and you must answer many k-th smallest queries. What would you change?
The walk costs O(H + k) for every query. To make it faster, store in each node the number of nodes in its left subtree. Then you can go left or right by comparing
kwith that count, and one query takes O(H). The count must be updated on every insert and every delete.- How do you do the same with recursion?
Write
inorder(node): call it onnode.left, then countnode, then call it onnode.right. Stop when the count reachesk. It has the same O(H + k) time. The call stack takes the place ofstack, so a very deep tree can exceed the recursion limit.- How do you find the smallest gap between two values in a BST?
The smallest gap is between two values that are next to each other in sorted order. Walk the tree in order, keep the previous value, and update the best gap with
node.val - prevat each visit. This is Minimum Absolute Difference in BST (LC 530). It takesO(N)time and O(H) space.
SWE Reasoning
Spot it
- The tree is a BST, and the question depends on the order or the rank of the values: k-th smallest, a gap between neighbours, the nearest values to a target.
- The wording says "in sorted order", "next smaller", "next larger" or asks for an iterator over the values.
- You can stop at some point, so a full pass over the tree is not needed.
- A value must be compared only with the value visited just before it.
- The call tree would be deep, so an explicit stack is safer than recursion.
The invariant, step by step
- The inner loop pushes
nodeand moves tonode.leftuntil there is no node. The top ofstackis then the smallest value that is not visited yet. node = stack.pop()visits the top. All values smaller thannode.valhave been visited. All nodes still onstackhold larger values.k -= 1counts this visit. Whenkreaches 0, this is the k-th visit, sonode.valis the k-th smallest.node = node.rightmoves to the right subtree. Its values are larger thannode.valand smaller than the next node onstack.- The loop runs while
nodeorstackhas something left, so no value is skipped. - Each node is pushed once and popped once. The walk visits the values in ascending order, one value per pop.
Traps
- Counting at the push. The root is pushed first and is not the smallest value. Count right after
stack.pop(). while stackas the outer loop. The stack is empty at the start, so the loop never runs. Usewhile node or stack.- Pushing
node.rightonto the stack. The left side of the right child is skipped. Setnode = node.rightand let the inner loop dive. - Reading the whole tree for a small
k. Return as soon askreaches 0. - Using it on a tree that is not a BST. The inorder order is sorted only for a BST.
Practice
Builds on BST Bounds and Tree Traversals, which you haven’t finished yet.
Inorder Traversal as a Sorted Stream (Kth Smallest in BST, BST Iterator)
You get the root of a binary search tree and a whole number k. Imagine writing every value in the tree in a row, smallest first, and numbering the positions from 1: return the value that lands in position k.
In a binary search tree, the values in a node's left subtree are smaller than the node's value, and the values in its right subtree are larger.
Follow-up: if nodes are inserted and deleted often and this question is asked again and again, how would you make each answer faster?
1, 2, 3, 4. Position 1 holds 1, a leaf on the left, even though 3 sits at the top of the tree.BST Inorder
BST ➔ inorder walk (left, node, right) ➔ values in sorted order| 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 kth_smallest(root: Optional[TreeNode], k: int) -> int: |
| 10 | """Kth Smallest Element in a BST: an inorder walk visits the values in sorted order. |
| 11 | Time: O(H + k) | Space: O(H) stack |
| 12 | """ |
| 13 | # Nodes whose left subtree is being walked; each waits for its visit |
| 14 | stack: list[TreeNode] = [] |
| 15 | node = root |
| 16 | while node or stack: |
| 17 | while node: # 1. Dive left: every smaller value sits in a left subtree |
| 18 | stack.append(node) |
| 19 | node = node.left |
| 20 | node = stack.pop() # 2. Visit: the smallest value not visited yet |
| 21 | k -= 1 # Count a node when it is visited, never when it is pushed |
| 22 | if k == 0: |
| 23 | return node.val # The k-th visit is the k-th smallest value |
| 24 | node = node.right # 3. Its right subtree holds the next larger values |
| 25 | return -1 # Never reached: 1 <= k <= n |
stack in ascending order: when stack.pop() returns node, every value smaller than node.val has already been visited, and every node still on stack holds a larger value.An inorder walk of a BST (left subtree, then the node, then the right subtree) visits the values in sorted order, so read the tree as a sorted list, one value per visit: count, compare or collect at the moment stack.pop() hands you a node, and stop as soon as you have the answer. The inner loop pushes node and moves to node.left until it falls off the tree, so when a node is popped, its left subtree has been visited, and so has every ancestor it sits to the right of: those are exactly the smaller values. node = node.right then moves on to the next larger values. The trap is where you count: k -= 1 belongs right after stack.pop(), not next to stack.append(node), because nodes are pushed from the root down, and on [3,1,4,null,2] counting pushes returns 3 for k = 1 instead of 1.
See it run
Inorder walk that stops at the k-th visit, step by step
k 3node 5answer not found yet
Each circle is a tree node. The stack row has its top on the right. The visited row shows the values in the order they were popped.
nodethe node the loop is looking aton stackpushed, and waiting for its left subtree to finishvisitedpopped and countedanswerthe k-th value popped
Start at the root 5 with k = 3. Dive left and push every node on the stack.
Gotcha 1 of 4
- The trap
Gotcha 1: Counting
k -= 1when a node is pushedMistakewhile node: stack.append(node) k -= 1 if k == 0: return node.val node = node.left node = stack.pop()Fixwhile node: stack.append(node) node = node.left node = stack.pop() k -= 1 if k == 0: return node.valWhat happens: A pushed node is only waiting for its visit. The pushes go from the root down, so the root is pushed first. The values come in sorted order only when nodes are popped. In the example, counting pushes stops at the root 3 for
k = 1. The smallest value is 1.Example: Kth Smallest Element in a BST (LC 230): root = [3,1,4,null,2], k = 1Mistake: returns 3Fix: returns 1
- You only need the one place where a value belongs, as in Insert into a Binary Search Tree (LC 701), not the values in order: a single path down from the root decides it. See BST Bounds
- The values arrive one at a time and are not kept in a BST, as in Kth Largest Element in a Stream (LC 703): there is no tree whose inorder walk hands you sorted order. See Top-K Heap
Deep Dive
Why values leave the stack in ascending order
In a BST (binary search tree), a node's left subtree holds smaller values and its right subtree holds larger values. An inorder walk visits the left subtree, then the node, then the right subtree. So a node is visited after all of its smaller values, and before all of its larger values.
The blueprint does this with a stack. The inner loop pushes node and moves to node.left until there is no node. The top of stack is then the smallest value that is not visited yet. stack.pop() visits it. Then node = node.right moves to the next larger values. Every node that stays on stack has not been visited yet, and each one holds a larger value than the node just popped.
Example: in Kth Smallest Element in a BST (LC 230), take root = [5, 3, 6, 2, 4, null, null, 1] and k = 3. The pushes are 5, 3, 2 and 1. The pops are 1, then 2, then 3. After the third pop, k is 0, so the answer is 3. The values came out in the order 1, 2, 3.
The trap: count when a node is popped, not when it is pushed
A node is pushed from the root down, so the first node pushed is the root. The root is not the smallest value. A pushed node is only waiting for its visit. The pop is the visit.
If k -= 1 sits next to stack.append(node), the count follows the pushes. On root = [3, 1, 4, null, 2] with k = 1, the first push is the root 3. The count reaches 0 there, so the function returns 3. The correct answer is 1.
Two more traps are in the loop. The outer condition must be while node or stack. At the start, stack is empty, so while stack never runs and the function returns -1. Also use node = node.right after the pop. If you push node.right onto stack instead, the dive into the left side of that right child is skipped. On [2, 1, 4, null, null, 3] with k = 3, that version returns 4. The correct answer is 3, because 3 is the left child of 4.
Stopping early, and the cost O(H + k)
The walk stops at the k-th visit. It does not read the whole tree. Before the first pop it pushes one node per level on the way to the leftmost node, so that is H pushes, where H is the height of the tree. After that, each pop and each right move is one more visit.
Example: the tree [4, 2, 6, 1, 3, 5, 7] has 7 nodes and height 3. With k = 1 the walk makes 3 pushes and 1 pop. With k = 7 it makes 7 pushes and 7 pops.
Compare this with building a list of all N values and then reading position k - 1. That always costs O(N) time. The stack holds at most H nodes, so the space is O(H). For a chain of 100 nodes that leans to the left, the walk makes 100 pushes before the first pop. That is the worst case for H.
Which problems read the sorted stream, and the neighbour cards
Once the walk gives the values in order, other questions are short. In Minimum Absolute Difference in BST (LC 530) and Minimum Distance Between BST Nodes (LC 783), the smallest gap is always between two values that are next to each other in sorted order. Keep the previous value and compare it with each new value.
In Closest Binary Search Tree Value II (LC 272), keep the last k visited values. When a new value is not closer to the target than the oldest kept value, stop. Every later value is larger and therefore farther.
BST Bounds is the neighbour card. In Insert into a Binary Search Tree (LC 701), one path from the root decides the answer, so you do not need the values in order. In Kth Largest Element in a Stream (LC 703), the values arrive one at a time and are not stored in a tree. There is no tree to walk in order.
60-Second Pitch
"In a BST, an inorder walk visits the values in ascending order. So the k-th visit is the k-th smallest value. I walk with an explicit stack. The inner loop pushes the node and moves left until it falls off the tree. Then I pop, which gives the smallest value not yet visited. I count there, and I return when k reaches 0. Then I move to the right child. I count at the pop and not at the push, because the push goes from the root down and the root is not the smallest. The time is O(H + k), because the first dive pushes H nodes and then each visit is cheap. The space is O(H) for the stack."
Common Questions
- Why does an inorder walk of a BST give sorted values?
The BST rule puts smaller values in the left subtree and larger values in the right subtree. Inorder visits left, then the node, then right. So a node comes after all smaller values and before all larger values. By induction, the whole walk is in ascending order.
- What is the time complexity of the Kth Smallest Element in a BST (LC 230) walk?
O(H + k). The first dive pushes about H nodes, where H is the height of the tree. Then each of the k visits does a small amount of work. The space is O(H) for the stack. A walk that first collects all values costs
O(N).- The tree changes often and you must answer many k-th smallest queries. What would you change?
The walk costs O(H + k) for every query. To make it faster, store in each node the number of nodes in its left subtree. Then you can go left or right by comparing
kwith that count, and one query takes O(H). The count must be updated on every insert and every delete.- How do you do the same with recursion?
Write
inorder(node): call it onnode.left, then countnode, then call it onnode.right. Stop when the count reachesk. It has the same O(H + k) time. The call stack takes the place ofstack, so a very deep tree can exceed the recursion limit.- How do you find the smallest gap between two values in a BST?
The smallest gap is between two values that are next to each other in sorted order. Walk the tree in order, keep the previous value, and update the best gap with
node.val - prevat each visit. This is Minimum Absolute Difference in BST (LC 530). It takesO(N)time and O(H) space.
SWE Reasoning
Spot it
- The tree is a BST, and the question depends on the order or the rank of the values: k-th smallest, a gap between neighbours, the nearest values to a target.
- The wording says "in sorted order", "next smaller", "next larger" or asks for an iterator over the values.
- You can stop at some point, so a full pass over the tree is not needed.
- A value must be compared only with the value visited just before it.
- The call tree would be deep, so an explicit stack is safer than recursion.
The invariant, step by step
- The inner loop pushes
nodeand moves tonode.leftuntil there is no node. The top ofstackis then the smallest value that is not visited yet. node = stack.pop()visits the top. All values smaller thannode.valhave been visited. All nodes still onstackhold larger values.k -= 1counts this visit. Whenkreaches 0, this is the k-th visit, sonode.valis the k-th smallest.node = node.rightmoves to the right subtree. Its values are larger thannode.valand smaller than the next node onstack.- The loop runs while
nodeorstackhas something left, so no value is skipped. - Each node is pushed once and popped once. The walk visits the values in ascending order, one value per pop.
Traps
- Counting at the push. The root is pushed first and is not the smallest value. Count right after
stack.pop(). while stackas the outer loop. The stack is empty at the start, so the loop never runs. Usewhile node or stack.- Pushing
node.rightonto the stack. The left side of the right child is skipped. Setnode = node.rightand let the inner loop dive. - Reading the whole tree for a small
k. Return as soon askreaches 0. - Using it on a tree that is not a BST. The inorder order is sorted only for a BST.