Binary Tree BasicsBinary tree basics

01Why it exists

Reach for it when you see:Hierarchy, nesting, parent and child, depth, height, leaves, left and right subtrees, complete binary trees.

02The core idea

A tree is a connected graph with no cycles, but the more intuitive description is this: one root node, with zero or more subtrees hanging beneath it, each of which is itself a tree. That self-referential definition is exactly why almost every tree algorithm is written recursively. A binary tree is one where each node has at most two children, split into a left subtree and a right subtree — and the two sides are not interchangeable.

A few terms you must keep straight. Depth is the number of edges from the root down to a node, so the root has depth 0. Height is the number of edges from a node down to its furthest leaf, so a leaf has height 0, and the tree's height is the root's height. A leaf has no children; an internal node has at least one. Depth counts downwards from the top, height counts upwards from the bottom — opposite directions.

A complete binary tree has every level filled, except possibly the last, which is filled from the left. That gives it a very useful property: number the nodes in level order 0, 1, 2, …, and the parent of index i is at (i − 1) / 2 while the children are at 2i + 1 and 2i + 2, with no gaps anywhere. This is exactly what lets a heap live in an array. A full binary tree is stricter still: every node has either no children or exactly two.

For a binary tree with n nodes, the smallest possible height is ⌊log₂ n⌋ (every level packed) and the largest is n − 1 (degenerated into a chain). Many structures later on have complexities written as O(h) for height h, and whether you can keep h ≈ log n is the subject of the lesson on balancing.

03The algorithm

1. 1For any tree problem, ask first: what is the answer for an empty tree? Height is −1, size is 0, sum is 0. That is the recursion's base case.
2. 2Now assume the left and right subtrees have already been solved (call them L and R): how do L, R and this node's own value combine into your answer? Height is 1 + max(L, R), size is 1 + L + R.
3. 3Write it as a function: handle the empty tree, recurse left and right, combine. Those three lines are the skeleton of almost every tree problem.
4. 4Work out the complexity: every node is visited exactly once, so O(n) time, and the recursion depth equals the tree's height, so O(h) space.
5. 5To build a tree for testing, use a level-order array with 2i + 1 and 2i + 2 — that is also LeetCode's input format.

04Interactive demo

Click any node to see its depth, height and subtree size on the right. The array underneath highlights where it sits in the level-order representation, and how the parent and child indices are computed.

05Code

The node definition, the three most basic recursive functions, and how to build a tree from a level-order array. Note that the base case for height is −1, which is what makes a leaf's height 0.

class TreeNode:
    def __init__(self, val, left=None, right=None):
        self.val = val
        self.left = left
        self.right = right


def height(node):
    """Height: the longest edge count going down from this node. An empty tree is -1, a leaf is 0."""
    if node is None:
        return -1
    return 1 + max(height(node.left), height(node.right))


def size(node):
    """Subtree size: the number of nodes, counting this one."""
    if node is None:
        return 0
    return 1 + size(node.left) + size(node.right)


def is_leaf(node):
    return node.left is None and node.right is None


def from_level_order(values):
    """Build a tree from a level-order array (None is an empty slot), the LeetCode input format."""
    if not values:
        return None
    nodes = [TreeNode(v) if v is not None else None for v in values]
    for i, node in enumerate(nodes):
        if node is None:
            continue
        l, r = 2 * i + 1, 2 * i + 2      # the index relation of a complete binary tree
        if l < len(nodes):
            node.left = nodes[l]
        if r < len(nodes):
            node.right = nodes[r]
    return nodes[0]


root = from_level_order([1, 2, 3, 4, 5, 6, 7])
print(height(root), size(root))   # 2 7

06Practice

• LeetCode 104Maximum Depth of Binary TreeEasy
• LeetCode 222Count Complete Tree Nodes (exploit the complete-tree property for O(log² n))Easy
• LeetCode 110Balanced Binary TreeEasy
• LeetCode 543Diameter of Binary TreeEasy
• LeetCode 226Invert Binary TreeEasy
• LeetCode 100Same TreeEasy