Binary Trees and Traversals

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.

Recursive and iterative traversals

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

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.

त्वरित जाँच: Which traversal of a binary search tree visits values in sorted order?

• In-order
• Pre-order
• Post-order
• Level-order