Binary Trees and Traversal Orders

Build the mental model

Where a linked list node points to only one next node, a binary tree node can point to up to two children — a left child and a right child. In tree terminology, the topmost node with no parent is the root, a node with no children is a leaf, the number of edges from the root to a node is its depth (or level), and the depth of the deepest leaf is the tree's height. Visiting every node can be done in different traversal orders: in-order (left, then node, then right) produces sorted order for a binary search tree; pre-order (node, then left, then right) is useful for serializing or copying a tree since the root gets processed first; post-order (left, then right, then node) is used when every child must be handled before its parent — deleting a directory tree, for instance, requires removing files (leaves) before the folders (parents) that contain them. All three orders are really just a recursive function visiting a recursively defined structure, differing only in when the node's own value is processed relative to its children.

Connect it to a real scenario

The Tutorial Platform's course category structure (course to chapter to sub-topic) can be modeled as a tree, using in-order traversal to build a table-of-contents sidebar and post-order traversal to safely archive a course by cleaning up sub-lessons before their parent chapters.

Each node can point to up to two children — left and right
In-order traversal produces sorted order from a binary search tree
Pre-order suits processing the root first; post-order suits processing children before the parent

Try the working example

python

class Node:
    def __init__(self, value, left=None, right=None):
        self.value = value
        self.left = left
        self.right = right

def in_order(node, result):
    if node is None:
        return result
    in_order(node.left, result)   # visit left subtree first
    result.append(node.value)     # then this node
    in_order(node.right, result)  # then right subtree
    return result

#        "queues"
#        /      \
# "hash-tables" "stacks"
root = Node("queues", Node("hash-tables"), Node("stacks"))
print(in_order(root, []))

You should see

Prints ["hash-tables", "queues", "stacks"] — the left child, then the root, then the right child, in that visiting order.

5-minute try-it

Write pre_order and post_order functions for the same tree and print all three outputs side by side to compare them.

One important caution

Forgetting the base case (if node is None: return) — recursion then tries to access None.left once it reaches a leaf, raising an AttributeError

Assuming in-order traversal always yields sorted output for any binary tree — that's only true when the BST invariant (left < node < right) holds, and this lesson's example tree isn't a BST

Wikipedia — Binary tree — Data Structures & Algorithms