# Binary Trees and Traversals — Data Structures in Python

Source: https://www.skillbyai.com/en/data-structures-python/t-binary

> Represent trees and traverse them recursively and iteratively.

## Hierarchical data

A **tree** is a hierarchy of **nodes** connected by edges, with a single **root** and no cycles; nodes without children are **leaves**. In a **binary tree**, each node has at most two children (left and right). Key measures are **depth** (distance from the root) and **height** (longest path to a leaf); a **balanced** tree with n nodes has height about log₂ n, which keeps operations fast. Trees model file systems, HTML documents (the DOM), organisation charts, expression parsing and decision trees, and underpin search trees, heaps and tries. **Traversals** visit every node: **depth-first** orders are **pre-order** (node, left, right: copy or serialise a tree), **in-order** (left, node, right: sorted order in a BST) and **post-order** (left, right, node: delete or evaluate children first); **breadth-first** (level-order) visits level by level using a queue. Recursive traversals are elegant but can hit Python's **recursion limit** (about 1,000 by default) on very deep, unbalanced trees; iterative versions with an explicit stack avoid that.

## Traversal orders

Pre-order, in-order, post-order and level-order visit the same tree in different sequences.

![A small binary tree with seven nodes, with four numbered sequences beside it, one for each traversal order.](assets/figures/data-structures-python/section-5-map.svg) — Figure 5.1 — Four ways to walk a binary tree.

## Recursive and iterative traversals

In-order recursively, pre-order with a stack and level-order with a deque.

```python
from __future__ import annotations
from collections import deque
from dataclasses import dataclass
from typing import Optional

@dataclass
class TreeNode:
    value: int
    left: Optional[TreeNode] = None
    right: Optional[TreeNode] = None

def inorder(node: Optional[TreeNode]) -> list[int]:
    if node is None:
        return []
    return inorder(node.left) + [node.value] + inorder(node.right)

def preorder_iterative(root: Optional[TreeNode]) -> list[int]:
    result, stack = [], [root] if root else []
    while stack:
        node = stack.pop()
        result.append(node.value)
        if node.right:
            stack.append(node.right)                # push right first so left is processed first
        if node.left:
            stack.append(node.left)
    return result

def level_order(root: Optional[TreeNode]) -> list[list[int]]:
    levels, queue = [], deque([root] if root else [])
    while queue:
        level = []
        for _ in range(len(queue)):
            node = queue.popleft()
            level.append(node.value)
            queue.extend(child for child in (node.left, node.right) if child)
        levels.append(level)
    return levels

def height(node: Optional[TreeNode]) -> int:
    return 0 if node is None else 1 + max(height(node.left), height(node.right))

#        4
#      /   \
#     2     6
#    / \   / \
#   1   3 5   7
root = TreeNode(4, TreeNode(2, TreeNode(1), TreeNode(3)), TreeNode(6, TreeNode(5), TreeNode(7)))
print(inorder(root))              # [1, 2, 3, 4, 5, 6, 7]
print(preorder_iterative(root))   # [4, 2, 1, 3, 6, 5, 7]
print(level_order(root))          # [[4], [2, 6], [1, 3, 5, 7]]
print(height(root))               # 3
```

## Mind the recursion limit

A degenerate tree built from sorted input is effectively a linked list, so recursive functions on it can exceed Python's recursion limit. Prefer iterative traversals for untrusted or very deep data instead of raising the limit.

**Quiz:** Which traversal of a binary search tree visits values in sorted order?

- [x] In-order
- [ ] Pre-order
- [ ] Post-order
- [ ] Level-order

*Answer:* In-order. In-order visits the left subtree, the node, then the right subtree.