Binary Trees

Hierarchical data, the structure behind file systems, compilers, and search

You have seen a tree before, even if nobody called it that.
Think of the folders on a computer. One folder at the top. Inside it, more folders. Inside those, more folders again. Or think of who reports to who at a school: the principal at the top, teachers under them, students under each teacher.
A binary tree is that same shape, with one small rule: each box has at most two boxes hanging under it. That is the whole idea. Two children, no more.
We use this shape for anything that branches: your files, a web page, a family line, the folders in your email.

Four words get used a lot with trees. They sound fancy. They are not. Tap each one on the tree below and it will show you exactly what it means.

Root, the one box at the very top

Leaf, a box at the bottom with nothing hanging under it

Height, how tall the tree is, counted in steps

Depth, how far down one box sits from the top

Tree node and basic operationspython

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

# Build a tree:
#       1
#      / \
#     2   3
#    / \
#   4   5
root = TreeNode(1,
    TreeNode(2, TreeNode(4), TreeNode(5)),
    TreeNode(3)
)

def height(node):
    if not node: return 0
    return 1 + max(height(node.left), height(node.right))

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

print(height(root))       # → 3
print(count_nodes(root))  # → 5

🤔Quick Check

A "balanced" binary tree has height O(log n) where n is the number of nodes. Why does this matter?

Practice Exercises

0/1 solved

Exercise 1 of 1easy

⏱ 00:00

Maximum Depth

Find the maximum depth (height) of a binary tree.
Expected output: 3

solution.py

1 / 1

Solve all 1 exercise to unlock completion

Previous Next