Binary Trees: Fundamentals

The Org Chart in Your Computer

Picture a company org chart. At the top sits the CEO. Reporting to her are two VPs. Each VP manages their own team of directors. Each director oversees their own managers. The structure fans outward and downward — a hierarchy where every person except the CEO has exactly one boss, and every person can manage at most a handful of people.

Now imagine that every person manages at most two direct reports. You have just described a binary tree.

A binary tree is one of the most fundamental and widely used data structures in computer science. File systems, HTML pages, compilers, decision trees, and database indexes all use tree structures at their core. Understanding binary trees is the foundation for understanding all of them.

Tree Terminology

Before writing any code, the vocabulary matters:

The tree above has:

• Root: 4
• Leaves: 1, 3, 5, 7
• Height of tree: 2 (longest path from root to a leaf)
• Height of node 2: 1

The Binary Tree Node

Every node in a binary tree holds three things: a value, a pointer to its left child, and a pointer to its right child. Missing children are None.

class TreeNode:
    def __init__(self, val):
        self.val = val          # The value stored at this node
        self.left = None        # Pointer to the left child (or None)
        self.right = None       # Pointer to the right child (or None)

That is the complete definition. Elegant in its simplicity.

Building a Tree Manually

# Build the tree:
#        4
#       / \
#      2   6
#     / \ / \
#    1  3 5  7

root = TreeNode(4)

root.left = TreeNode(2)
root.right = TreeNode(6)

root.left.left = TreeNode(1)
root.left.right = TreeNode(3)

root.right.left = TreeNode(5)
root.right.right = TreeNode(7)

print(root.val)              # 4
print(root.left.val)         # 2
print(root.left.right.val)   # 3

Height and Depth: Recursive Calculations

The height of a tree is naturally recursive: the height of any node is one plus the maximum height of its two children. The height of None is -1 (or 0 if you count nodes instead of edges — be consistent).

def height(node):
    if node is None:
        return -1                         # Empty tree has height -1
    left_height = height(node.left)       # Height of left subtree
    right_height = height(node.right)     # Height of right subtree
    return 1 + max(left_height, right_height)  # Add 1 for the current node

print(height(root))          # 2
print(height(root.left))     # 1
print(height(root.left.left)) # 0  (leaf node)

The depth of a specific node requires tracking how far down you went while searching:

def depth(root, target, current_depth=0):
    if root is None:
        return -1                             # Target not found
    if root.val == target:
        return current_depth                  # Found it — return how deep we are
    # Search left subtree first
    left = depth(root.left, target, current_depth + 1)
    if left != -1:
        return left
    # Then search right subtree
    return depth(root.right, target, current_depth + 1)

print(depth(root, 4))   # 0 — root
print(depth(root, 2))   # 1
print(depth(root, 7))   # 2
print(depth(root, 9))   # -1 — not in tree

Output:

0
1
2
-1

Counting Nodes

def count_nodes(node):
    if node is None:
        return 0
    return 1 + count_nodes(node.left) + count_nodes(node.right)

print(count_nodes(root))    # 7

Types of Binary Trees

Not all binary trees are created equal. These classifications matter for performance guarantees:

Why does balance matter? A perfectly balanced tree of n nodes has height O(log n). A degenerate tree has height O(n). Since most tree operations traverse from root to leaf, this difference is the gap between O(log n) and O(n) performance.

Why Trees Matter: Hierarchical Data Is Everywhere

Trees are not an academic curiosity. They model the structure of the real world:

File Systems — A folder contains subfolders and files. Subfolders contain more subfolders. The root is / or C:\. Every path from root to file follows a branch of the tree.

HTML / DOM — Every web page is a tree. The <html> element is the root. It contains <head> and <body>. Each contains its own children. JavaScript's document.querySelector() searches this tree.

Decision Trees in Machine Learning — A model that makes predictions by asking yes/no questions. Each internal node asks a question; each leaf gives an answer. The depth of the tree controls model complexity.

Expression Trees in Compilers — The expression (3 + 5) * 2 becomes a tree where * is the root, 2 is the right child, and + is the left child with 3 and 5 as its children. Evaluating the tree gives the result.

Database B-Trees — The index structures in databases like PostgreSQL and MySQL use balanced tree variants (B-trees, B+ trees) to keep data sorted and searchable in O(log n).

Binary Tree Properties: Quick Reference

For a perfect binary tree of height h:

• Total nodes: 2^(h+1) - 1
• Leaf nodes: 2^h
• At height 10: 2,047 nodes — a small tree holds a lot

For a balanced binary tree of n nodes:

• Height: O(log n)
• This is why balanced trees are so powerful

Key Takeaway

A binary tree is any structure where each node has at most two children. The power comes from hierarchy: data arranged in a tree can be searched, inserted, and deleted in O(log n) time when the tree is balanced. This single property — logarithmic height — is what separates efficient tree-based algorithms from brute-force linear search. Everything that comes next — binary search trees, heaps, AVL trees, tries — builds on this foundation.