visualization

DFS Inorder Traversal

Left, visit, right — and a BST reads itself out in sorted order.

BST · root 4 · left subtree {2,1,3} · right subtree {6,5,7}step 1/21

recursion stack (top last) · emitted so far

inorder(4)emitted → —

Call inorder(4) and push it on the stack — but don't emit 4 yet; its whole left subtree must come first.

pseudocode

def inorder(node):
    if node is None:
        return
    inorder(node.left)    # everything smaller first
    visit(node)           # emit the value
    inorder(node.right)   # everything bigger after
# BST + inorder = sorted output