Understanding Binary Trees: Core Concepts, Traversals, and Python Implementations

What is a Binary Tree?

A binary tree is an inverted tree where the root is at the top and each node can have at most two children: a left child and a right child; a third child is not allowed.

Key terminology (interview essentials)

Root node: the topmost node with no parent.

Parent/child relationship: hierarchical links between nodes.

Leaf node: a node without any children.

Depth: the number of levels from the root down to a node.

Height: the maximum number of levels from a node down to its deepest leaf.

Four common binary tree shapes

Ordinary binary tree: nodes are placed arbitrarily, each with up to two children.

Full binary tree: every internal node has exactly two children and all leaves reside on the same level.

Complete binary tree: all levels are completely filled except possibly the last, which is left‑aligned.

Degenerate (skewed) tree: each node has only a left child or only a right child, effectively forming a linked list and degrading performance.

Core traversals (order of visiting nodes)

The left child is always visited before the right; only the position of the root changes among the traversals.

Pre‑order: root → left → right.

In‑order: left → root → right (produces a sorted sequence for binary search trees).

Post‑order: left → right → root.

Level‑order: breadth‑first from top to bottom, left to right, implemented with a queue.

Python implementation (run‑ready)

from collections import deque

# 定义二叉树节点
class TreeNode:
    def __init__(self, val):
        self.val = val
        self.left = None
        self.right = None

# 前序遍历 根-左-右
def pre_order(node, res):
    if not node:
        return
    res.append(node.val)
    pre_order(node.left, res)
    pre_order(node.right, res)

# 中序遍历 左-根-右
def in_order(node, res):
    if not node:
        return
    in_order(node.left, res)
    res.append(node.val)
    in_order(node.right, res)

# 后序遍历 左-右-根
def post_order(node, res):
    if not node:
        return
    post_order(node.left, res)
    post_order(node.right, res)
    res.append(node.val)

# 层序遍历（队列实现）
def level_order(root):
    if not root:
        return []
    q = deque([root])
    out = []
    while q:
        node = q.popleft()
        out.append(node.val)
        if node.left:
            q.append(node.left)
        if node.right:
            q.append(node.right)
    return out

# ==========构建一颗测试二叉树==========
if __name__ == "__main__":
    # 手动搭建树结构
    root = TreeNode(1)
    root.left = TreeNode(2)
    root.right = TreeNode(3)
    root.left.left = TreeNode(4)
    root.left.right = TreeNode(5)
    root.right.right = TreeNode(6)

    pre = []
    pre_order(root, pre)
    print("前序遍历：", pre)

    mid = []
    in_order(root, mid)
    print("中序遍历：", mid)

    post = []
    post_order(root, post)
    print("后序遍历：", post)

    print("层序遍历：", level_order(root))

Sample output

Pre‑order: 1, 2, 4, 5, 3, 6

In‑order: 4, 2, 5, 1, 3, 6

Post‑order: 4, 5, 2, 6, 3, 1

Level‑order: 1, 2, 3, 4, 5, 6

Real‑world applications

File system directories: folders act as parent nodes, sub‑folders/files as children.

Database indexes: B+ trees are multi‑way tree structures underlying indexes.

AI decision trees and syntax parse trees.

Heap sort and priority queues built on complete binary trees.

HTML DOM tree: the entire page forms a large tree.

Common pitfalls for beginners

Forgetting the recursion base case (if not node) causes stack overflow.

Swapping left and right children changes traversal order and results.

Degenerate trees degrade to O(n) performance, similar to linked lists.

Deep recursion may overflow the call stack; use an explicit stack to simulate recursion when needed.