Binary Tree Fundamentals

Jr Codex DSA Notes

Level: Intermediate Prerequisites: Module 6, Chapter 4 Time to complete: ~20 minutes

Table of Contents

1. What Is a Binary Tree?
2. Key Terminology
3. The Node Class
4. Building a Tree by Hand
5. Why Height Governs Complexity
6. Balanced vs. Skewed Trees
7. Summary & Next Steps

1. What Is a Binary Tree?

A binary tree is a linked structure (Module 6) where each node has at most two children, conventionally called left and right, instead of a single next. This branching is what makes trees suited to representing hierarchy — file systems, organization charts, decision logic — and, with an ordering rule added (Chapter 3), efficient search.

        8
       / \
      3   10
     / \    \
    1   6    14
       / \   /
      4   7 13

2. Key Terminology

In the tree above, 10's height is 1, and 4's depth is 3 — these two numbers together describe how "spread out" or "narrow" the tree is, which turns out to be the single biggest factor in how fast tree operations run (Section 5).

3. The Node Class

class Node:
    def __init__(self, value):
        self.value = value
        self.left = None
        self.right = None

Structurally identical to the linked list Node from Module 6, except next has been replaced with two pointers — this is the entire conceptual leap from "list" to "tree."

4. Building a Tree by Hand

root = Node(8)
root.left = Node(3)
root.right = Node(10)
root.left.left = Node(1)
root.left.right = Node(6)
root.right.right = Node(14)
root.left.right.left = Node(4)
root.left.right.right = Node(7)
root.right.right.left = Node(13)

As with linked lists, wiring nodes by hand doesn't scale — Chapter 3 introduces an insert function that builds a tree automatically, following the BST ordering rule.

5. Why Height Governs Complexity

Nearly every tree operation — search, insert, delete — works by starting at the root and moving down one level at a time, choosing left or right at each step. The number of steps such an operation takes is bounded by the tree's height, not the number of nodes directly:

def max_depth(node):
    if node is None:
        return 0
    return 1 + max(max_depth(node.left), max_depth(node.right))
    # Visits every node once → O(n) time, O(h) space for the recursion stack,
    # where h is the tree's height

This is why Chapter 3 will draw a sharp distinction between a balanced tree (height ≈ log n) and a skewed one (height ≈ n) — the same operation can be O(log n) or O(n) purely depending on the tree's shape, echoing the best/worst-case framing from Module 1, Chapter 5.

6. Balanced vs. Skewed Trees

Balanced (height = 2, n = 7):        Skewed (height = 6, n = 7):
        4                                    1
      /   \                                   \
     2     6                                   2
    / \   / \                                   \
   1   3 5   7                                   3
                                                    \
                                                     4
                                                      \
                                                       ...

A balanced tree keeps its height close to log n by ensuring left and right subtrees stay roughly equal in size at every node. A skewed tree — for example, one built by inserting already-sorted data into a naive BST (Chapter 3) — degenerates toward a structure that behaves like a linked list, with height approaching n. Self-balancing trees (AVL, Red-Black) solve this by rebalancing on every insert, but are out of scope for this curriculum's interview-prep focus — what matters here is recognizing why the distinction changes an algorithm's complexity.

7. Summary & Next Steps

Key Takeaways

• A binary tree node has at most two children (left, right) — structurally, just a linked-list node with an extra pointer.
• Height (longest root-to-leaf path) — not node count — bounds how many steps most tree operations take.
• A balanced tree has height ≈ log n; a skewed tree can have height ≈ n, degenerating toward linked-list-like behavior.
• Recursive tree functions typically run in O(n) time (visiting every node) with O(h) space (the recursion stack), where h is the tree's height.

Concept Check

1. Why does a node's height matter more for algorithm speed than the total number of nodes in the tree?
2. What input pattern would cause a naive BST insert (Chapter 3) to build a skewed tree?
3. In max_depth, why is the space complexity O(h) rather than O(n)?

Next Chapter

→ Chapter 2: Tree Traversals

Jr Codex — 1-on-1 Personalized Coaching | Back to Module Index