Binary Trees

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

A binary tree is a hierarchical structure where each node has at most 2 children (left and right). Trees are the natural data structure for hierarchical data: file systems, HTML DOM, organization charts, expression evaluation.
Key terms:

Root, top node (no parent)

Leaf, node with no children

Height, longest path from root to leaf

Depth, distance from root to a node

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