Validate BST and In-Order Properties
Validate a binary tree as a BST using min/max bounds passed down the tree and by checking that in-order traversal produces a sorted sequence.
Validate BST and In-Order Properties is a free DSA Interview Prep lesson on CoddyKit — lesson 3 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.
The BST Validation Problem
Validate BST (LeetCode #98) is a classic interview problem that trips up many candidates. The naive approach checks only that each node's value is greater than its left child and less than its right child, but this local check is insufficient. A subtree node might satisfy the local rule yet violate the global BST property. The correct solution propagates valid min/max bounds down the tree.
class TreeNode:
def __init__(self, val=0, left=None, right=None):
self.val = val
self.left = left
self.right = right
# Why local check fails:
# 5
# / \
# 1 4
# / \
# 3 6
# Node 4's children (3, 6) satisfy local rule,
# but 4 < 5 and is in the RIGHT subtree -- BST violated!
print('Local check is insufficient -- use min/max bounds')Min/Max Bounds Approach
Pass lower and upper bounds down the recursion. At each node, verify that low < node.val < high. When recursing left, update the upper bound to node.val (left subtree must be less). When recursing right, update the lower bound to node.val (right subtree must be greater). Start with low = -infinity and high = +infinity.
def is_valid_bst(root, low=float('-inf'), high=float('inf')):
if not root:
return True
if not (low < root.val < high):
return False
return (is_valid_bst(root.left, low, root.val) and
is_valid_bst(root.right, root.val, high))
# Valid BST:
valid = TreeNode(5)
valid.left = TreeNode(3)
valid.right = TreeNode(7)
print(is_valid_bst(valid)) # True
# Invalid BST (3 is in wrong subtree conceptually):
invalid = TreeNode(5)
invalid.left = TreeNode(1)
invalid.right = TreeNode(4)
invalid.right.left = TreeNode(3)
invalid.right.right = TreeNode(6)
print(is_valid_bst(invalid)) # False (4 < 5 in right subtree)In-Order Traversal Validation
An alternative validation approach uses the BST's in-order sorted property: collect the in-order sequence and verify it is strictly increasing. This is elegant and easy to reason about. However, it uses O(n) extra space to store the sequence. An optimised version uses a single prev pointer during traversal to check each pair without storing the whole sequence.
def is_valid_bst_inorder(root):
prev = [float('-inf')]
def inorder(node):
if not node:
return True
if not inorder(node.left):
return False
if node.val <= prev[0]: # not strictly increasing
return False
prev[0] = node.val
return inorder(node.right)
return inorder(root)
valid = TreeNode(5)
valid.left = TreeNode(3)
valid.right = TreeNode(7)
valid.left.left = TreeNode(1)
valid.left.right = TreeNode(4)
print(is_valid_bst_inorder(valid)) # True
invalid = TreeNode(5)
invalid.left = TreeNode(6) # 6 > 5 in left subtree!
print(is_valid_bst_inorder(invalid)) # FalseComparing Both Validation Approaches
The min/max bounds approach is O(n) time and O(h) space (only the bounds on the call stack). The in-order prev-pointer approach is also O(n) time and O(h) space. Both are optimal. The min/max approach is more general and works cleanly when extended to problems with additional constraints. In interviews, be ready to present both and discuss trade-offs — showing awareness of alternatives is a strong signal.
# Both approaches:
# Time: O(n) -- visit each node once
# Space: O(h) -- call stack depth
# h = O(log n) balanced, O(n) skewed
# When to choose which:
# min/max bounds:
# - Cleaner for trees with constraints beyond BST
# - No global state (purely functional)
# in-order prev:
# - More intuitive (sorted sequence check)
# - Easier to convert to iterative with a stack
print('Both O(n) time, O(h) space -- choose by clarity')Recover BST: Two Swapped Nodes
Recover BST (LeetCode #99) repairs a BST where exactly two nodes are swapped. During in-order traversal, a correctly ordered BST produces a sorted sequence. If two nodes are swapped, there will be one or two violations where prev.val > current.val. The first node of the first violation and the second node of the last violation are the two misplaced nodes — swap their values.
def recover_tree(root):
first = second = prev = None
def inorder(node):
nonlocal first, second, prev
if not node:
return
inorder(node.left)
if prev and prev.val > node.val:
if not first:
first = prev # first violator
second = node # always update second
prev = node
inorder(node.right)
inorder(root)
# Swap values of the two misplaced nodes
if first and second:
first.val, second.val = second.val, first.val
root = TreeNode(3)
root.left = TreeNode(1)
root.right = TreeNode(4)
root.right.left = TreeNode(2) # 2 and 3 are swapped
recover_tree(root)
print(root.val, root.right.left.val) # 2, 3 (fixed)BST In-Order to Sorted Array
Converting a BST to a sorted array is trivial: perform in-order traversal and collect values. This O(n) time and O(n) space operation is a quick way to leverage sorted-array algorithms (binary search, two pointers) on BST data. It is often a stepping stone in multi-part BST problems like 'merge two BSTs' or 'find median of BST'.
def bst_to_sorted_array(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(4)
root.left = TreeNode(2)
root.right = TreeNode(6)
root.left.left = TreeNode(1)
root.left.right = TreeNode(3)
root.right.left = TreeNode(5)
root.right.right = TreeNode(7)
print(bst_to_sorted_array(root)) # [1, 2, 3, 4, 5, 6, 7]Merging Two BSTs
To merge two BSTs into one sorted array, convert each to a sorted array in O(n) and O(m), then merge the two sorted arrays using the merge step of merge sort in O(n+m). Total time: O(n+m). If you need the result as a balanced BST, feed the merged sorted array to the sorted-array-to-BST algorithm. This decomposition into simple sub-problems is the mark of a clear interviewer-friendly solution.
def merge_two_bsts(root1, root2):
def inorder(node, arr):
if not node:
return
inorder(node.left, arr)
arr.append(node.val)
inorder(node.right, arr)
arr1, arr2 = [], []
inorder(root1, arr1)
inorder(root2, arr2)
# Merge two sorted arrays
merged = []
i = j = 0
while i < len(arr1) and j < len(arr2):
if arr1[i] <= arr2[j]:
merged.append(arr1[i]); i += 1
else:
merged.append(arr2[j]); j += 1
merged.extend(arr1[i:])
merged.extend(arr2[j:])
return merged
r1 = TreeNode(2); r1.left = TreeNode(1); r1.right = TreeNode(4)
r2 = TreeNode(3); r2.left = TreeNode(0); r2.right = TreeNode(5)
print(merge_two_bsts(r1, r2)) # [0, 1, 2, 3, 4, 5]Count Nodes in BST Range
Count how many nodes have values in the range [low, high]. A brute-force in-order scan is O(n). The BST-aware version prunes: if the current node's value is less than low, there is no point checking the left subtree (all values there are also less than low). Similarly prune the right subtree when the current value is greater than high. Average case is O(log n + k) where k is the count of matching nodes.
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 may have values >= low
total += range_sum_bst(root.left, low, high)
if root.val < high: # right subtree may 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 = 32Duplicate Values and Strict vs Non-Strict BST
The standard BST invariant uses strict inequality: left subtree values are strictly less and right subtree values are strictly greater. Some problems allow duplicates, placing them in the left subtree (left <= root) or right subtree (root < right). When validating BSTs, always check the problem statement's definition. The min/max bounds approach handles both variants by adjusting whether the bound check is strict or inclusive.
# Strict BST (LeetCode default): left < root < right
def is_valid_strict(root, lo=float('-inf'), hi=float('inf')):
if not root:
return True
if not (lo < root.val < hi): # STRICT inequalities
return False
return (is_valid_strict(root.left, lo, root.val) and
is_valid_strict(root.right, root.val, hi))
# Non-strict BST (allows duplicates in right): left <= root < right
def is_valid_nonstrict(root, lo=float('-inf'), hi=float('inf')):
if not root:
return True
if not (lo <= root.val < hi): # NOTE: <= for left side
return False
return (is_valid_nonstrict(root.left, lo, root.val + 1) and
is_valid_nonstrict(root.right, root.val, hi))
print('Always clarify strict vs non-strict with interviewer')In-Order as Universal BST Tool
The in-order traversal is the Swiss Army knife of BST problems. Whenever a BST problem asks about sorted order, kth element, range queries, or sequence properties, consider whether an in-order scan (or its reverse) gives you the answer. Most BST-specific problems reduce to: traverse in sorted order and do something at each step. Recognising this mapping quickly is a key interview skill.
# Problems solved elegantly with in-order:
# 1. Validate BST: check prev <= curr during in-order
# 2. Kth smallest: count k steps in in-order
# 3. Kth largest: count k steps in REVERSE in-order
# 4. Closest value to target: find crossover in in-order
# 5. BST to sorted array: collect in-order into list
# 6. Recover BST: find 1-2 violations in in-order
# 7. Sum of range [lo, hi]: accumulate during in-order
# The key insight: in-order visits BST nodes in sorted order.
# All sorted-order reasoning translates to in-order DFS.
print('In-order = sorted access = foundation of BST reasoning')Closest Value in BST
Find the node whose value is closest to a given target. Use the BST's ordering: start at the root, track the closest value seen so far, and navigate toward the target (go left if target is less, right if greater). This O(h) approach is more efficient than an in-order scan and demonstrates effective use of the BST property to prune search space.
def closest_value(root, target):
closest = root.val
curr = root
while curr:
if abs(curr.val - target) < abs(closest - target):
closest = curr.val
if target < curr.val:
curr = curr.left
elif target > curr.val:
curr = curr.right
else:
break # exact match
return closest
root = TreeNode(4)
root.left = TreeNode(2)
root.right = TreeNode(5)
root.left.left = TreeNode(1)
root.left.right = TreeNode(3)
print(closest_value(root, 3.714286)) # 4Quick Check
Test your understanding of Data Structures & Algorithms — Coding Interview Prep concepts from this lesson.
Lesson Recap
In this lesson you learned: BST validation with min/max bounds (avoiding the local-check pitfall), the in-order prev-pointer alternative for validation, and in-order as the universal BST tool for range sums, closest value, and merge operations. Next up we use BST in-order properties to find the kth smallest element.
Frequently asked questions
Is the “Validate BST and In-Order Properties” lesson free?
Yes — the full text of “Validate BST and In-Order Properties” 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 “Validate BST and In-Order Properties”?
Validate a binary tree as a BST using min/max bounds passed down the tree and by checking that in-order traversal produces a sorted sequence. 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 3 of 4, so you can start here or from the beginning and move at your own pace.
How long does the “Validate BST and In-Order Properties” 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