Trees and Traversals — Core Concepts

Why trees matter

Trees are the natural data structure for hierarchical data. File systems, HTML/XML documents, database indices, abstract syntax trees in compilers, and decision trees in machine learning all use tree structures. Understanding trees and their traversal patterns is essential for working with any of these systems.

Binary tree basics

A binary tree is a tree where each node has at most two children:

class TreeNode:
    def __init__(self, val, left=None, right=None):
        self.val = val
        self.left = left
        self.right = right

Building a sample tree:

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

tree = TreeNode(1,
    TreeNode(2, TreeNode(4), TreeNode(5)),
    TreeNode(3, None, TreeNode(6))
)

The four traversal patterns

1. Pre-order (root → left → right)

Visit the current node first, then recurse on children:

def preorder(node):
    if not node:
        return []
    return [node.val] + preorder(node.left) + preorder(node.right)

# Result: [1, 2, 4, 5, 3, 6]

Use case: Copying a tree, serializing a tree to a file, prefix expression evaluation.

2. In-order (left → root → right)

Visit the left subtree, then the current node, then the right subtree:

def inorder(node):
    if not node:
        return []
    return inorder(node.left) + [node.val] + inorder(node.right)

# Result: [4, 2, 5, 1, 3, 6]

Use case: For a binary search tree, in-order traversal produces elements in sorted order.

3. Post-order (left → right → root)

Visit both children first, then the current node:

def postorder(node):
    if not node:
        return []
    return postorder(node.left) + postorder(node.right) + [node.val]

# Result: [4, 5, 2, 6, 3, 1]

Use case: Deleting a tree (free children before parent), calculating directory sizes, postfix expression evaluation.

4. Level-order (breadth-first)

Visit all nodes at depth 0, then depth 1, then depth 2:

from collections import deque

def level_order(root):
    if not root:
        return []
    result = []
    queue = deque([root])
    while queue:
        node = queue.popleft()
        result.append(node.val)
        if node.left:
            queue.append(node.left)
        if node.right:
            queue.append(node.right)
    return result

# Result: [1, 2, 3, 4, 5, 6]

Use case: Finding the shortest path in a tree, printing a tree level by level.

Binary search trees (BST)

A BST enforces an ordering rule: for every node, all values in the left subtree are smaller, and all values in the right subtree are larger.

class BST:
    def __init__(self):
        self.root = None
    
    def insert(self, val):
        self.root = self._insert(self.root, val)
    
    def _insert(self, node, val):
        if not node:
            return TreeNode(val)
        if val < node.val:
            node.left = self._insert(node.left, val)
        elif val > node.val:
            node.right = self._insert(node.right, val)
        return node
    
    def search(self, val):
        return self._search(self.root, val)
    
    def _search(self, node, val):
        if not node:
            return False
        if val == node.val:
            return True
        elif val < node.val:
            return self._search(node.left, val)
        else:
            return self._search(node.right, val)

BST operations are O(h) where h is the height. For a balanced tree, h = O(log n). For a degenerate tree (all nodes in one direction), h = O(n).

Tree properties

Property	Definition
Height	Longest path from root to any leaf
Depth	Distance from root to a specific node
Balanced	Left and right subtree heights differ by at most 1
Complete	Every level is fully filled except possibly the last
Full	Every node has either 0 or 2 children

def height(node):
    if not node:
        return -1  # empty tree has height -1
    return 1 + max(height(node.left), height(node.right))

def is_balanced(node):
    if not node:
        return True
    left_h = height(node.left)
    right_h = height(node.right)
    return (abs(left_h - right_h) <= 1 and 
            is_balanced(node.left) and 
            is_balanced(node.right))

Common misconception

“Trees are just for interviews.” Trees power some of the most critical systems: B-trees in databases enable fast disk-based queries, tries enable autocomplete, syntax trees power every programming language compiler, and DOM trees structure every web page. If you work with structured data, you work with trees.

One thing to remember: The four traversal patterns — pre-order, in-order, post-order, and level-order — are your toolkit for every tree problem. Most tree algorithms are variations of these four patterns.