DSA In-order Traversal
In-order traversal visits the left subtree, then the root, then the right subtree, and on a binary search tree this simple rule outputs every value in sorted order.
What Is In-order Traversal?
In-order traversal is a depth-first strategy that processes nodes in left, root, right order. At each node, you first recursively traverse its entire left subtree, then visit the node itself, and finally recursively traverse its entire right subtree. The node sits in between its two subtrees in the visiting order, which is where the name comes from.
In-order traversal is most useful on a binary search tree: because every node's left subtree holds smaller values and its right subtree holds larger ones, visiting left, root, right at every level produces the tree's values in ascending sorted order, with no separate sorting step required. On a general expression tree, in-order also prints infix notation, since it places each operator between its two operands.
Recursive In-order Traversal
Example: Recursive In-order on a BST
class Node:
def __init__(self, value, left=None, right=None):
self.value = value
self.left = left
self.right = right
def inorder(node, result=None):
if result is None:
result = []
if node is None:
return result
inorder(node.left, result)
result.append(node.value)
inorder(node.right, result)
return result
# Tree: root 8; left child 3, right child 10.
# 3's children are 1 and 6; 6's children are 4 and 7.
# 10's right child is 14, and 14's left child is 13.
root = Node(8,
Node(3, Node(1), Node(6, Node(4), Node(7))),
Node(10, None, Node(14, Node(13))))
print(inorder(root))
# [1, 3, 4, 6, 7, 8, 10, 13, 14]Iterative In-order Traversal (Using a Stack)
The iterative version simulates recursion with an explicit stack: walk down the left spine of the tree, pushing every node along the way, until there's nowhere left to go. Then pop a node, visit it, and move to its right child, repeating the left-spine walk from there. This produces exactly the same order as the recursive version without making recursive calls.
Example: Iterative In-order
class Node:
def __init__(self, value, left=None, right=None):
self.value = value
self.left = left
self.right = right
def inorder_iterative(root):
result = []
stack = []
current = root
while stack or current:
while current: # walk down the left spine
stack.append(current)
current = current.left
current = stack.pop() # visit the node
result.append(current.value)
current = current.right # then explore the right subtree
return result
root = Node(8,
Node(3, Node(1), Node(6, Node(4), Node(7))),
Node(10, None, Node(14, Node(13))))
print(inorder_iterative(root))
# [1, 3, 4, 6, 7, 8, 10, 13, 14]Example: Validating a BST with In-order
class Node:
def __init__(self, value, left=None, right=None):
self.value = value
self.left = left
self.right = right
def inorder(node, result=None):
if result is None:
result = []
if node is None:
return result
inorder(node.left, result)
result.append(node.value)
inorder(node.right, result)
return result
def is_valid_bst(root):
values = inorder(root)
return all(values[i] < values[i + 1] for i in range(len(values) - 1))
good_tree = Node(8, Node(3, Node(1), Node(6)), Node(10, None, Node(14)))
bad_tree = Node(8, Node(3, Node(1), Node(9)), Node(10)) # 9 sits left of 8 but is bigger
print(is_valid_bst(good_tree)) # True
print(is_valid_bst(bad_tree)) # False- Visit order is left subtree, then root, then right subtree
- On a binary search tree, in-order output is always sorted ascending
- Reversing the pattern to right, root, left yields descending order instead
- Used to print infix expressions from an expression tree
- Runs in O(n) time and O(h) extra space, where h is the tree's height
