Validate a BST and Sorted Output with Inorder
30 min · Intermediate
Need help? Ask a tutor on WhatsApp (opens in a new tab)A tree handed to you may not be a BST at all. Two tools settle it: walking the tree left, node, right gives the keys in order, and passing bounds down checks the rule on every node in one pass.
Inorder gives sorted keys
Inorder traversal visits the left subtree, then the node itself, then the right subtree. On a binary search tree it produces the keys in increasing order.
Visit the left subtree, then the node, then the right subtree. In a BST everything on the left is smaller and everything on the right is larger, so the keys come out in increasing order.
def inorder(node): if node is not None: yield from inorder(node.left) yield node.key yield from inorder(node.right)yield from hands over every key of the inner call. This is a generator, so it makes keys one at a time and can be stopped early. It uses O(h) stack and visits n nodes, so the time is O(n).
Check by sorted output
A tree is a BST exactly when its inorder keys strictly increase. A check that only compares each node with its two children is not enough, because a bad key can sit deeper.
def is_bst(root): keys = list(inorder(root)) return all(a < b for a, b in pairwise(keys))Example 1 · A tree that fails by one deep key
class Node: def __init__(self, key): self.key = key self.left = None self.right = None
def insert(node, key): if node is None: return Node(key) if key < node.key: node.left = insert(node.left, key) elif key > node.key: node.right = insert(node.right, key) return node
def inorder(node): if node is not None: yield from inorder(node.left) yield node.key yield from inorder(node.right)
from itertools import pairwisedef is_bst(root): keys = list(inorder(root)) return all(a < b for a, b in pairwise(keys))
root = Node(5)root.left = Node(3)root.right = Node(8)root.right.left = Node(4)print(list(inorder(root)))print(is_bst(root))[3, 5, 4, 8] False
What this code does
- Node 4 is the left child of 8, so it passes the check against its parent. But it is in the right subtree of 5, where every key must be larger than 5.
- The inorder keys 3, 5, 4, 8 are not increasing, which exposes it.
pairwise gives each key with the next one. Strictly increasing also rejects duplicates. This uses O(n) extra space for the list.
Check with bounds
Every node must lie between a low and a high bound. Going left, the node's key becomes the new high. Going right, it becomes the new low. This needs no list and uses only O(h) stack.
def is_bst(node, low=None, high=None): if node is None: return True if low is not None and node.key <= low: return False if high is not None and node.key >= high: return False return is_bst(node.left, low, node.key) and is_bst(node.right, node.key, high)Example 2 · Validate with bounds
class Node: def __init__(self, key): self.key = key self.left = None self.right = None
def is_bst(node, low=None, high=None): if node is None: return True if low is not None and node.key <= low: return False if high is not None and node.key >= high: return False return is_bst(node.left, low, node.key) and is_bst(node.right, node.key, high)
root = Node(5)root.left = Node(3)root.right = Node(8)root.right.left = Node(4)print(is_bst(root))root.right.left = Noneprint(is_bst(root))False True
What this code does
- Going right from 5 sets low to 5. Node 4 is then not larger than the low bound, so the check fails at once.
- With 4 removed, the tree is a valid BST.
None means no bound yet. The checks use <= and >=, so an equal key fails.
Reading a tree from one line
A tree can be written as keys in level order, row by row, with # for a missing child. So 8 3 10 # 6 is a root 8 with children 3 and 10, and 3 has no left child and a right child 6.
def build(tokens): if not tokens or tokens[0] == "#": return None root = Node(int(tokens[0])) queue = deque([root]) rest = iter(tokens[1:]) while queue: node = queue.popleft() for side in ("left", "right"): token = next(rest, "#") if token != "#": child = Node(int(token)) setattr(node, side, child) queue.append(child) return rootExample 3 · Read a tree from text
class Node: def __init__(self, key): self.key = key self.left = None self.right = None
from collections import deque
def build(tokens): if not tokens or tokens[0] == "#": return None root = Node(int(tokens[0])) queue = deque([root]) rest = iter(tokens[1:]) while queue: node = queue.popleft() for side in ("left", "right"): token = next(rest, "#") if token != "#": child = Node(int(token)) setattr(node, side, child) queue.append(child) return root
def inorder(node): if node is not None: yield from inorder(node.left) yield node.key yield from inorder(node.right)
tokens = "8 3 10 1 6 # 14 # # 4 7 13".split()root = build(tokens)print(root.left.right.left.key)print(root.right.right.left.key)print(*inorder(root))4 13 1 3 4 6 7 8 10 13 14
What this code does
- The tokens are level order: 8; then 3 and 10; then the children of 3 (1 and 6); then 10 has no left child (#) and right child 14; and so on.
- The same text also describes trees that are not BSTs, which is what a validate problem needs.
Example 4 · Stop at the first problem
class Node: def __init__(self, key): self.key = key self.left = None self.right = None
from collections import deque
def build(tokens): if not tokens or tokens[0] == "#": return None root = Node(int(tokens[0])) queue = deque([root]) rest = iter(tokens[1:]) while queue: node = queue.popleft() for side in ("left", "right"): token = next(rest, "#") if token != "#": child = Node(int(token)) setattr(node, side, child) queue.append(child) return root
def inorder(node): if node is not None: yield from inorder(node.left) yield node.key yield from inorder(node.right)
def first_bad(root): previous = None for key in inorder(root): if previous is not None and key <= previous: return key previous = key return None
print(first_bad(build("5 3 8 # # 4".split())))print(first_bad(build("5 3 8".split())))4 None
What this code does
- The generator makes keys one at a time, so the loop stops at the first key that breaks the order. The rest of the tree is not visited.
- Return
Nonewhen no key breaks the order.
Example 5 · A tree can be a chain and still valid
class Node: def __init__(self, key): self.key = key self.left = None self.right = None
from collections import deque
def build(tokens): if not tokens or tokens[0] == "#": return None root = Node(int(tokens[0])) queue = deque([root]) rest = iter(tokens[1:]) while queue: node = queue.popleft() for side in ("left", "right"): token = next(rest, "#") if token != "#": child = Node(int(token)) setattr(node, side, child) queue.append(child) return root
def inorder(node): if node is not None: yield from inorder(node.left) yield node.key yield from inorder(node.right)
from itertools import pairwisedef is_bst(root): keys = list(inorder(root)) return all(a < b for a, b in pairwise(keys))
chain = build("1 # 2 # 3 # 4".split())print(*inorder(chain))print(is_bst(chain))print(is_bst(build("2 2 3".split())))1 2 3 4 True False
What this code does
- Each key has only a right child. The shape is bad for speed, but the rule holds.
- Equal keys fail the strict check, so
2 2 3is not a BST here.
A queue holds nodes that still need children. Each node takes the next two tokens, left then right, and a missing token means no child. Put from collections import deque at the top.
Next step
Check your understanding
11 quick questions