Trees & Binary Trees: Terminology, Traversals (In/Pre/Post/Level-Order), and Recursion

In plain words: the org chart analogy

Think of a company's org chart. At the top sits the CEO (the root). Below the CEO are the VPs (children), below each VP are the directors, below them the managers, and so on down to individual contributors (leaves) who report to someone but have no one reporting to them. The whole structure is a tree: no cycles, one clear top, and every node reachable from the root along a unique path. File systems, HTML documents, JSON payloads, expression trees in compilers, and decision processes all have this same shape.

Everything so far has been linear — elements in a row. But an enormous amount of real data is hierarchical. The tree is the structure of hierarchy, and it's also where recursion stops being a technique and becomes the native language: a tree is *defined* recursively (a node plus subtrees, which are themselves trees), so recursive code mirrors the data exactly.

Anatomy and vocabulary

               1          ← root (depth 0, height 3)
             /   \
            2     3        ← depth 1
           / \     \
          4   5     6      ← depth 2
         /
        7                  ← leaf, depth 3 (height 0)

Node 2: parent=1, children={4,5}, subtree={2,4,5,7}
Node 4: parent=2, child={7}
Node 7: leaf (no children), depth=3, height=0
Tree height = height of root = 3 (edges from root to deepest leaf)

• Depth of a node: edges from the root down to it (root = depth 0).
• Height of a node: edges on the longest path from it down to a leaf (leaf = height 0). Height of the tree = height of the root.
• Height vs depth: depth is measured top-down, height bottom-up. A tree of n nodes has height between log₂(n) (perfectly bushy) and n − 1 (a chain). Nearly every tree complexity in the next four lessons is written in terms of height h.
• Subtree: any node together with all its descendants forms a valid tree — this recursive structure is why tree code is recursive.

A tree is a set of nodes connected by edges such that there's exactly one path between any two nodes — no cycles. One node is the root; every node except the root has exactly one parent; nodes it points to are its children; nodes with no children are leaves. Nodes sharing a parent are siblings.

Binary trees and their shapes

A binary tree restricts every node to at most two children, distinguished as left and right (the order matters). A node is one value plus two child references; the whole structure hangs off a single root reference, exactly as a linked list hangs off its head.

FULL              COMPLETE          PERFECT          DEGENERATE
(0 or 2 kids)     (left-fills last)  (all same depth)  (chain)

     1                  1                  1               1
    / \               /   \              /   \              \
   2   3             2     3            2     3              2
  / \               / \   /           / \   / \              \
 4   5             4   5 6           4   5 6   7              3
                                                               \
                                                                4

Full: every      Complete: all      Perfect: 2^(h+1)-1  Degenerate:
node has 0       levels full        total nodes,        effectively
or 2 children    except possibly    all leaves at       a linked list
                 the last           the same depth      h = n-1

The four traversals

Linear structures have one natural visiting order; trees have several, and choosing the right one is often the whole solution. The three depth-first orders differ only in when the current node is processed relative to its subtrees:

# Depth-first: the skeleton is identical; only the print position changes

def preorder(node):           # node FIRST
    if node is null: return
    visit(node)
    preorder(node.left)
    preorder(node.right)

def inorder(node):            # node BETWEEN children
    if node is null: return
    inorder(node.left)
    visit(node)
    inorder(node.right)

def postorder(node):          # node LAST
    if node is null: return
    postorder(node.left)
    postorder(node.right)
    visit(node)

def levelorder(root):         # breadth-first; uses a QUEUE
    if root is null: return
    queue = Queue()
    queue.enqueue(root)
    while not queue.isEmpty():
        node = queue.dequeue()
        visit(node)
        if node.left:  queue.enqueue(node.left)
        if node.right: queue.enqueue(node.right)

1. Preorder (node, left, right): process the node first, then recurse left, then right. Use when parents must precede children — copying/serializing a tree, printing a directory with indentation, prefix expression notation.
2. Inorder (left, node, right): recurse left, process the node, recurse right. On a binary search tree this visits keys in sorted order — the single most important traversal fact in the course.
3. Postorder (left, right, node): recurse into both children before the node. Use when children must precede parents — computing directory sizes, deleting/freeing a tree, evaluating expression trees (operands before the operator).
4. Level-order (BFS): visit depth 0, then depth 1, then 2 … Implemented with a queue from Lesson 7: enqueue the root; repeatedly dequeue a node, process it, enqueue its children. Use for anything phrased 'level by level' — and it's the tree-shaped preview of graph BFS.

One tree, four orders — traced

Tree:
        1
       / \
      2   3
     / \
    4   5

Preorder   (node, L, R):  1 → 2 → 4 → 5 → 3
  Visit 1, go left → visit 2, go left → visit 4 (leaf),
  backtrack → go right → visit 5 (leaf), backtrack → visit 3 (leaf)

Inorder    (L, node, R):  4 → 2 → 5 → 1 → 3
  Go left all the way to 4 (leaf, visit), backtrack → visit 2,
  go right → visit 5, backtrack → visit 1, go right → visit 3

Postorder  (L, R, node):  4 → 5 → 2 → 3 → 1
  Recurse both children fully before visiting: 4, 5, then 2; 3; then 1

Level-order (BFS queue):   1 → 2 → 3 → 4 → 5
  Enqueue 1; dequeue 1 (visit), enqueue 2,3
  Dequeue 2 (visit), enqueue 4,5; Dequeue 3 (visit)
  Dequeue 4 (visit); Dequeue 5 (visit)

The recursive template in action

Nearly every tree problem is the same skeleton: base case for the empty tree, recurse on both children, combine. Three canonical examples, each three lines of logic:

def height(node):
    if node is null: return -1        # base case (counting edges)
    return 1 + max(height(node.left), height(node.right))

def count(node):
    if node is null: return 0
    return 1 + count(node.left) + count(node.right)

def invert(node):
    if node is null: return null
    node.left, node.right = invert(node.right), invert(node.left)
    return node

# All three: O(n) time, O(h) stack space.

• Height: height(null) = −1; otherwise 1 + max(height(left), height(right)).
• Count nodes: count(null) = 0; otherwise 1 + count(left) + count(right).
• Mirror/invert: invert(null) = null; swap the (already inverted) children via recursive calls.

All three are O(n) time, O(h) stack space — the leap of faith from Lesson 8 verbatim: assume the recursion handles the subtrees, write only the combine step. Harder-sounding problems — is it symmetric? are two trees identical? what's the max path sum? — are the same skeleton with a richer combine.

Worked example: is this tree height-balanced?

A tree is height-balanced if every node's two subtrees differ in height by at most 1. Naive approach: at each node, compute both subtree heights (O(n) each) and recurse — O(n²) on a degenerate tree, because deep nodes get re-measured over and over.

SENTINEL = -2   # signals "imbalanced found below, stop"

def checkBalance(node):
    if node is null: return -1           # base case: empty tree has height -1

    hl = checkBalance(node.left)
    if hl == SENTINEL: return SENTINEL   # imbalance below — short-circuit

    hr = checkBalance(node.right)
    if hr == SENTINEL: return SENTINEL

    if abs(hl - hr) > 1: return SENTINEL # this node is imbalanced

    return 1 + max(hl, hr)              # return height for the caller

def isBalanced(root):
    return checkBalance(root) != SENTINEL

# One postorder pass — each node visited exactly once: O(n) time, O(h) space.

Common pitfalls

• Forgetting the null base case. The empty tree is a valid tree, and it's the base case of everything. Every recursive tree function starts 'if node is null…'.
• Confusing height and depth. Height counts up from leaves, depth counts down from the root. Off-by-one bugs breed at this boundary — also decide whether you count edges (leaf height 0) or nodes (leaf height 1) and stay consistent.
• Recomputing subtree properties. The O(n²) balanced-check above. If a parent needs a fact about its subtrees, have the recursion return it.
• Choosing the wrong traversal. Parents-before-children work requires preorder; children-before-parents work requires postorder. Picking the wrong one forces awkward second passes.
• Ignoring stack depth on degenerate trees. A tree that's secretly a 100,000-node chain overflows recursive traversal. If shape is untrusted, use an explicit stack or level-order.

Choosing the right traversal for the job

Practice problems

1. Maximum depth of a binary tree: return the number of edges (or nodes — pick one convention) on the longest root-to-leaf path. Write the recursive one-liner and trace it on a height-3 tree.
2. Symmetric tree: given a binary tree, determine whether it is a mirror image of itself. Hint: write a helper that compares two nodes — left.left vs right.right and left.right vs right.left.
3. Level-order traversal: return a list of lists, one sublist per level. Hint: track level size by counting nodes in the queue at the start of each level iteration.

Key takeaways

• Trees model hierarchy: one root, one parent per node, no cycles; every subtree is itself a tree — which is why recursion fits perfectly.
• Height h ranges from log₂(n) (bushy) to n − 1 (chain), and tree operation costs are written in h. Keeping h logarithmic is the business of Lessons 11–12.
• Preorder/inorder/postorder differ only in when the node is processed; level-order swaps recursion for a queue. All are O(n) time.
• Inorder on a BST yields sorted order — carry that into the next lesson.
• The universal template: null base case, recurse both sides, combine — and return subtree facts upward rather than recomputing them.

Next, trees earn their keep: add one ordering rule and you get the binary search tree — a structure that searches, inserts, *and* stays sorted. Practice traversal questions in the **AI Learning app**.

AI Learning: AI/ML/DS Q&A

A private, offline app to learn Artificial Intelligence, Machine Learning & Data Science at your own level: ~10,000 Q&A, illustrated guides, cheat sheets, quizzes and mock tests.

Coming soon toGoogle Play