Kth Smallest, Range Sum, and BST to Sorted Array
Leverage the sorted in-order traversal to find the kth-smallest element in O(k) and sum values within a range in O(log n + k).
Kth Smallest, Range Sum, and BST to Sorted Array is a free DSA Interview Prep lesson on CoddyKit — lesson 4 of 4. You can read the complete lesson below for free — then practise it hands-on in the browser with a built-in code editor and a 24/7 AI tutor. It is part of the DSA Interview Prep learning path, one of 4 lessons in the course, and your progress syncs across the web and the CoddyKit app.
Kth Smallest in a BST
Kth Smallest Element in a BST (LeetCode #230) is a classic problem that directly exploits the sorted in-order traversal. Since in-order visits nodes in ascending order, we simply count nodes as we traverse and return the value at count k. Time is O(h + k) where h is the height (to reach the leftmost node) and k is the number of steps in the in-order walk.
class TreeNode:
def __init__(self, val=0, left=None, right=None):
self.val = val
self.left = left
self.right = right
def kth_smallest(root, k):
count = [0]
result = [None]
def inorder(node):
if not node or result[0] is not None:
return
inorder(node.left)
count[0] += 1
if count[0] == k:
result[0] = node.val
return
inorder(node.right)
inorder(root)
return result[0]
root = TreeNode(3)
root.left = TreeNode(1)
root.right = TreeNode(4)
root.left.right = TreeNode(2)
print(kth_smallest(root, 1)) # 1
print(kth_smallest(root, 2)) # 2Kth Smallest: Iterative with Stack
The iterative version uses the explicit-stack in-order pattern. Push left nodes until null, then pop and count. When count reaches k, return the current node's value. This avoids Python's recursion limit for very deep trees and is equally O(h + k) time and O(h) space. Interviewers often ask for the iterative version after the recursive one.
def kth_smallest_iterative(root, k):
stack = []
curr = root
count = 0
while curr or stack:
while curr: # go as far left as possible
stack.append(curr)
curr = curr.left
curr = stack.pop() # process node
count += 1
if count == k:
return curr.val
curr = curr.right # move to right subtree
return -1 # k out of range
root = TreeNode(5)
root.left = TreeNode(3)
root.right = TreeNode(6)
root.left.left = TreeNode(2)
root.left.right = TreeNode(4)
root.left.left.left = TreeNode(1)
print(kth_smallest_iterative(root, 3)) # 3Kth Largest in a BST
Kth Largest uses reverse in-order traversal (right → root → left), which visits nodes in descending order. Count k steps and return the current node's value. This is symmetric to kth-smallest and runs in O(h + k) time. Alternatively, compute kth_smallest(root, total_count - k + 1) if you know the tree size, but the reverse in-order approach is more elegant.
def kth_largest(root, k):
count = [0]
result = [None]
def reverse_inorder(node):
if not node or result[0] is not None:
return
reverse_inorder(node.right) # visit LARGER values first
count[0] += 1
if count[0] == k:
result[0] = node.val
return
reverse_inorder(node.left)
reverse_inorder(root)
return result[0]
root = TreeNode(3)
root.left = TreeNode(1)
root.right = TreeNode(4)
root.left.right = TreeNode(2)
print(kth_largest(root, 1)) # 4 (largest)
print(kth_largest(root, 2)) # 3 (2nd largest)Range Sum of BST
Range Sum of BST (LeetCode #938) asks for the sum of all values in [low, high]. Exploit the BST property to prune: if the current node's value is less than low, the entire left subtree is also below low — skip it. If the current value is greater than high, skip the right subtree. This prunes many branches and is more efficient than a full in-order scan.
def range_sum_bst(root, low, high):
if not root:
return 0
total = 0
if low <= root.val <= high:
total += root.val
if root.val > low: # left subtree might have values >= low
total += range_sum_bst(root.left, low, high)
if root.val < high: # right subtree might have values <= high
total += range_sum_bst(root.right, low, high)
return total
root = TreeNode(10)
root.left = TreeNode(5)
root.right = TreeNode(15)
root.left.left = TreeNode(3)
root.left.right = TreeNode(7)
root.right.right = TreeNode(18)
print(range_sum_bst(root, 7, 15)) # 7+10+15 = 32Count Nodes in Range
Counting nodes in a range [low, high] follows the same pruning logic. An alternative uses bisect_left/bisect_right on the in-order array — but the direct BST traversal is O(log n + k) while converting to array first is always O(n). Choose direct traversal unless you need to answer many range queries, in which case building an augmented BST with subtree counts enables O(log n) per query.
def count_range(root, low, high):
if not root:
return 0
count = 0
if low <= root.val <= high:
count += 1
if root.val > low:
count += count_range(root.left, low, high)
if root.val < high:
count += count_range(root.right, low, high)
return count
root = TreeNode(10)
root.left = TreeNode(5)
root.right = TreeNode(15)
root.left.left = TreeNode(3)
root.left.right = TreeNode(7)
root.right.right = TreeNode(18)
print(count_range(root, 6, 15)) # 7, 10, 15 = 3BST to Sorted Array (Full Algorithm)
Converting a BST to a sorted array is O(n) time and O(n) space. Use in-order traversal and append each value. This is the starting point for multi-step problems: 'merge two BSTs', 'find the median of a BST', or 'check if two BSTs have the same in-order sequence'. The resulting array supports O(1) access by index, binary search, and two-pointer techniques that the BST itself cannot provide directly.
def bst_to_sorted(root):
result = []
def inorder(node):
if not node:
return
inorder(node.left)
result.append(node.val)
inorder(node.right)
inorder(root)
return result
root = TreeNode(5)
root.left = TreeNode(3)
root.right = TreeNode(8)
root.left.left = TreeNode(1)
root.left.right = TreeNode(4)
root.right.left = TreeNode(6)
root.right.right = TreeNode(9)
print(bst_to_sorted(root)) # [1, 3, 4, 5, 6, 8, 9]
# Binary search on the resulting sorted array:
import bisect
arr = bst_to_sorted(root)
print(bisect.bisect_left(arr, 6)) # 4 (index of 6)Augmented BST: Subtree Sizes
An augmented BST stores additional information at each node, such as the size of its subtree. With subtree sizes, kth-smallest becomes O(log n): at each node, if left subtree size is k-1, the current node is the answer; if left size >= k, recurse left; else subtract and recurse right. This is the data structure behind order-statistic trees used in competitive programming.
class AugNode:
def __init__(self, val):
self.val = val
self.left = None
self.right = None
self.size = 1 # subtree size
def get_size(node):
return node.size if node else 0
def update_size(node):
if node:
node.size = 1 + get_size(node.left) + get_size(node.right)
def kth_smallest_aug(root, k):
left_size = get_size(root.left)
if k == left_size + 1:
return root.val # current node is kth
elif k <= left_size:
return kth_smallest_aug(root.left, k)
else:
return kth_smallest_aug(root.right, k - left_size - 1)
print('Augmented BST: O(log n) kth smallest with subtree sizes')Find All Values in BST Between Two Nodes
To return all values strictly between two nodes p and q (where p.val < q.val), combine in-order traversal with range pruning: start collecting values once you pass p.val and stop after q.val. This is a generalisation of range sum and gives you the sorted sequence between the two query values in O(h + k) time.
def values_between(root, low, high):
result = []
def inorder(node):
if not node:
return
if node.val > low: # might be values > low on left
inorder(node.left)
if low < node.val < high: # strictly between
result.append(node.val)
if node.val < high: # might be values < high on right
inorder(node.right)
inorder(root)
return result
root = TreeNode(10)
root.left = TreeNode(5)
root.right = TreeNode(15)
root.left.left = TreeNode(3)
root.left.right = TreeNode(7)
root.right.left = TreeNode(12)
root.right.right = TreeNode(18)
print(values_between(root, 6, 15)) # [7, 10, 12]Median of BST
The median of a BST is the middle value of the in-order traversal. For n nodes, the median is at index n // 2 (0-indexed). Either collect the full sorted array and index into it, or use two passes: first count n nodes, then do a second in-order traversal stopping at the n // 2-th node. Alternatively, use the kth-smallest with k = n // 2 + 1.
def count_nodes(root):
if not root:
return 0
return 1 + count_nodes(root.left) + count_nodes(root.right)
def median_of_bst(root):
n = count_nodes(root)
if n == 0:
return None
k = n // 2 + 1 # (n+1)/2-th element for odd, n/2+1-th for even
return kth_smallest(root, k)
def kth_smallest(root, k):
count = [0]; result = [None]
def inorder(node):
if not node or result[0] is not None: return
inorder(node.left)
count[0] += 1
if count[0] == k: result[0] = node.val; return
inorder(node.right)
inorder(root); return result[0]
root = TreeNode(5)
root.left = TreeNode(3)
root.right = TreeNode(8)
root.left.left = TreeNode(1)
root.left.right = TreeNode(4)
print(median_of_bst(root)) # 4 (middle of [1,3,4,5,8])Closest K Values to Target
Find the k values in a BST closest to a target. A two-pointer approach: convert to sorted array and use a sliding window of size k. Alternatively, use a max-heap of size k where you push distances and pop when size exceeds k. The sorted-array approach is O(n) time and simple; the heap approach is O(n log k) but works in a streaming context.
import heapq
def closest_k_values(root, target, k):
# Collect sorted values
arr = []
def inorder(node):
if not node: return
inorder(node.left)
arr.append(node.val)
inorder(node.right)
inorder(root)
# Two-pointer sliding window of size k
left, right = 0, k - 1
while right < len(arr) - 1:
if abs(arr[left] - target) <= abs(arr[right + 1] - target):
break # left is closer, don't advance
left += 1
right += 1
return arr[left:right + 1]
root = TreeNode(4)
root.left = TreeNode(2)
root.right = TreeNode(5)
root.left.left = TreeNode(1)
root.left.right = TreeNode(3)
print(closest_k_values(root, 3.7, 2)) # [3, 4]Successor Order Property Exploited
Many BST problems reduce to finding the next or previous element in sorted order — operations that are O(log n) using BST navigation. The iterator we built earlier gives O(1) amortised next. Combining kth-smallest, range sum, and closest-value knowledge, you can solve most BST interview problems by asking: 'How does sorted ordering of in-order traversal simplify this?' This meta-pattern is your BST problem-solving compass.
# Meta-pattern for BST problems:
# Step 1: What sorted-order property does this exploit?
# Step 2: Is in-order (ascending) or reverse in-order (descending) needed?
# Step 3: Can I prune using BST ordering to avoid O(n) scan?
# Quick reference:
# kth smallest -> in-order, stop at kth node
# kth largest -> reverse in-order, stop at kth node
# range sum -> in-order + BST pruning
# closest value -> walk toward target, track best
# median -> kth with k = n//2+1
# sorted array -> full in-order
# validate -> in-order prev check or min/max bounds
print('Sorted in-order is the universal BST problem tool')Quick Check
Test your understanding of Data Structures & Algorithms — Coding Interview Prep concepts from this lesson.
Lesson Recap
In this lesson you learned: kth smallest and largest using in-order and reverse in-order traversal in O(h+k), range sum with BST pruning for efficient range queries, and converting a BST to a sorted array as a foundation for array-based algorithms. Next up we explore heaps and priority queues.
Frequently asked questions
Is the “Kth Smallest, Range Sum, and BST to Sorted Array” lesson free?
Yes — the full text of “Kth Smallest, Range Sum, and BST to Sorted Array” is free to read here on the web, and the DSA Interview Prep course includes 4 lessons in total. To practise it interactively (a built-in code editor and a 24/7 AI tutor) and unlock the rest of the DSA Interview Prep course, upgrade to CoddyKit PRO.
What will I learn in “Kth Smallest, Range Sum, and BST to Sorted Array”?
Leverage the sorted in-order traversal to find the kth-smallest element in O(k) and sum values within a range in O(log n + k). You practise DSA Interview Prep with hands-on code you run directly in the browser, and a 24/7 AI tutor answers your questions as you work through the lesson.
Do I need any experience to start DSA Interview Prep?
No prior experience is required. DSA Interview Prep on CoddyKit is structured for beginners through advanced learners; this is — lesson 4 of 4, so you can start here or from the beginning and move at your own pace.
How long does the “Kth Smallest, Range Sum, and BST to Sorted Array” lesson take?
Most CoddyKit lessons take about 5–10 minutes. Each one is bite-sized and interactive, so you make steady progress and pick up exactly where you left off across the web and the app.
Can I write and run code in this DSA Interview Prep lesson?
Yes. Every DSA Interview Prep lesson includes a built-in code editor, so you write and run real code right in your browser and get instant AI feedback — no local setup required.
All lessons in this course
- BST Insert and Search
- BST Delete: Three Cases
- Validate BST and In-Order Properties
- Kth Smallest, Range Sum, and BST to Sorted Array