Welcome to the branchy world of the binary tree python edition! 🌳 A binary tree is a hierarchical structure where each node holds a value and points to at most two children — a left and a right. That tiny rule unlocks file systems, database indexes, parsers, ML decision trees, and the DOM. Trees model relationships: parent/child, bigger/smaller, before/after.

They're foundational because almost every fast lookup structure is a tree in disguise. Once recursion on a tree clicks, recursion everywhere else clicks too. Let's grow some roots.

Anatomy of a Binary Tree

Here's a tiny tree:

        50          <- root (depth 0)
       /  \
     30    70       <- internal nodes
    / \   / \
  20  40 60  80    <- leaves

Root: the topmost node (50). Every tree has exactly one.

Parent / child: 30 is the parent of 20 and 40.

Leaf: a node with no children (20, 40, 60, 80).

Internal node: any non-leaf node.

Depth: distance from the root. Root has depth 0.

Height: longest path from root to any leaf. This tree has height 2.

Level: all nodes at the same depth.

Subtree: any node plus everything below it is itself a tree — which is why recursion works so well here.

Binary Tree Types

Not all binary trees are created equal. The shape matters — a lot.

Full binary tree: every node has either 0 or 2 children. No only-children allowed.

Complete binary tree: every level is filled except possibly the last, which fills left-to-right. Heaps live here.

Perfect binary tree: full and every leaf sits at the same depth. A flawless triangle.

Balanced binary tree: the height of left and right subtrees of every node differ by at most 1.

Degenerate (pathological) tree: each parent has only one child — basically a linked list wearing a tree costume. Performance disaster.

Binary Search Tree (BST): for every node, all values in the left subtree are smaller and all values on the right are larger. Our code is a BST implementation.

AVL tree: a self-balancing BST that re-balances on insert/delete using rotations, keeping height ≈ log n.

Red-black tree: a self-balancing BST with looser balance rules but cheaper rebalancing — used in many language standard libraries.

Tree Traversals

A tree traversal is the order you visit nodes. Four flavors:

1. In-order (Left → Root → Right): on a BST, outputs values in sorted order.

2. Pre-order (Root → Left → Right): great for copying or serializing a tree.

3. Post-order (Left → Right → Root): use for safe deletion (free leaves first) and evaluating expression trees bottom-up.

4. Level-order / BFS: use a queue. Perfect for shortest path in an unweighted tree, tree height, or printing level by level.

Recursive vs Iterative Traversal

The code above uses a recursive tree approach because trees are recursive by nature. But Python's call stack caps around 1000 frames, so for deep trees switch to iteration:

Iterative DFS: use a list as a stack. Push the root, then loop: pop, visit, push right child, push left.

Iterative BFS: use collections.deque as a queue. Append children right, popleft to visit.

Complexity Analysis

Operation	Balanced BST	Unbalanced BST	Notes
Search	O(log n)	O(n)	Halving the search space each step
Insert	O(log n)	O(n)	Same path as search
Delete	O(log n)	O(n)	Plus successor lookup
Traversal (any)	O(n)	O(n)	You must visit every node
Space (recursion)	O(log n)	O(n)	Call stack depth = tree height
Space (storage)	O(n)	O(n)	One node per value

The headline: a balanced tree is exponentially faster than an unbalanced one. Balance is not optional in production.

Common Pitfalls

Forgetting `None` checks: every recursive step should bail when node is None. Skip this and you'll meet AttributeError: 'NoneType' object has no attribute 'left' fast.

Comparing nodes by reference vs value: node1 == node2 checks identity unless you implement __eq__. To compare contents, compare .value, not the node objects.

Unbalanced trees from sorted input: inserting [1, 2, 3, 4, 5] into a vanilla BST creates a degenerate spine — O(log n) becomes O(n). Shuffle first, or use AVL/red-black.

Infinite loops in iterative traversal: forgetting to mark visited or pushing a node twice will spin forever. Always pop then push children, never the other way around.

Treating BST as a hash set: BSTs are great for ordered operations (range queries, min, max). For pure membership checks with no ordering, a set crushes them.

Mutable default arguments: def inorder(node, result=[]) shares the list across calls. Use result=None and initialize inside.

Real-World Uses

Binary trees and their cousins are everywhere:

File systems: NTFS, HFS+, and most modern FSs use B-tree / B+ tree variants.

Database indexes: PostgreSQL, MySQL, SQLite — almost every index is a B-tree variant.

Expression parsers / ASTs: every Python program is parsed into an Abstract Syntax Tree.

Decision trees in ML: scikit-learn's DecisionTreeClassifier, random forests, XGBoost.

Huffman coding: the file-compression classic builds an optimal prefix tree.

Autocomplete tries: a related tree where each node represents a character.

HTML/XML DOM: every webpage is a tree your browser walks.

Syntax highlighting: editors parse code into trees to color-code tokens.

When NOT to Use a Binary Tree

Need O(1) membership/lookup with no ordering? Use a set or dict.

Need indexed random access by position? Use a list or array.

Need just the min or max repeatedly? Use a heap (heapq) — it's a complete binary tree but the API is way simpler.

Tiny dataset (under ~50 items)? Linear scan is simpler and often faster.

Frequently Asked Questions

What's the difference between a binary tree and a BST? A binary tree is the shape — at most two children per node. A BST adds the ordering rule: left < parent < right. All BSTs are binary trees; not all binary trees are BSTs.

Why use a tree instead of a list? Lists give you O(n) search. A balanced BST gives you O(log n) search, insert, and ordered traversal. For 1M items, that's ~20 comparisons vs ~1,000,000.

How do I balance a binary tree? Two options: (1) use a self-balancing variant (AVL or red-black) that rebalances via rotations, or (2) for static data, sort the input and recursively pick the middle element as the root.

What's the max depth of a binary tree with N nodes? Worst case (degenerate): N - 1. Best case (balanced): lfloor log_2 N rfloor.

Is Python's `heapq` a binary tree? Yes — a complete binary tree (min-heap) stored in a flat list using index math (parent = (i-1)//2, children = 2i+1, 2i+2).

How do I serialize a tree? Pre-order traversal with explicit None markers ("50,30,20,#,#,40,#,#,70,#,#") is the simplest reversible format. Level-order also works.

Now run the code, mess with the numbers, and try writing the iterative versions yourself! 🌱

Binary Tree in Python

Try it yourself

How it works