Trees

Hierarchical Data Structures

CS205 Data Structures

Use arrow keys or buttons to navigate

What Is a Tree?

A tree is a hierarchical data structure of nodes connected by edges.

Click any node to explore

Root — topmost node (no parent)
Children — nodes directly below a node
Parent — the node directly above
Leaves — nodes with no children
Edge — connection between parent and child

Analogy: Family Tree

One ancestor at the top, descendants branching down. Or a file system: root folder with subfolders and files.

Key Property

n nodes → exactly n − 1 edges. There is exactly one path between any two nodes.

Tree Terminology

Click any node to see its properties

Root — node with no parent (A)
Siblings — same parent (B, C, D)
Ancestor of E — B, A
Descendant of B — E, F
Leaf / External — no children
Internal node — has children
Depth — edges from root to node
Height — edges on longest path down to a leaf
Subtree rooted at B — B, E, F

Height of tree = max depth of any leaf

Formal Definition of a Tree

Recursive Definition

A tree T is either:

Empty (null / no nodes), OR
A root node r with zero or more subtrees T₁, T₂, ..., T_k

Key Property

A tree with n nodes always has exactly n − 1 edges. Exactly one path between any two nodes (no cycles!).

Think Recursively

Every node is the root of its own subtree. "Zoom in" on any node and you see a smaller tree. Click the buttons to see this in action!

Tree ADT

Accessor Methods

Method	Description
`root()`	Return root node
`parent(v)`	Return parent of v
`children(v)`	Return children of v
`size()`	Number of nodes

depth(v):
  if isRoot(v): return 0
  return 1 + depth(parent(v))
 
height(T):
  if isExternal(T): return 0
  h = 0
  for each child c: h = max(h, height(c))
  return 1 + h

depth() goes UP, height() goes DOWN

Depth and Height

Click a node to see its depth path (↑) and height path (↓)

Depth of a Node

depth(v) = edges from root to v.
Root has depth 0. Goes top-down ↓.

Height of a Node

height(v) = edges on longest path from v down to a leaf.
Leaves have height 0. Goes bottom-up ↑.

Height of Tree

height(T) = height of root = max depth of any leaf.
Here: height(A) = 3 (path A → B → D → F).

Binary Trees

Each node has at most 2 children: a left and a right child.

Properties of Binary Trees

Property	Formula	Current
Max nodes at depth d	2^d	—
Max total nodes	2^h+1 − 1	—
Min height (n nodes)	⌊log₂ n⌋	—
Actual height	—	—

Why Binary?

Binary trees enable efficient searching, sorting, and expression evaluation. The most common tree in CS.

Left vs Right Matters!

A node with one child — it matters whether it's the left or right child. They are structurally different.

Full vs Complete vs Perfect Binary Trees

Full Binary Tree

Every node has 0 or 2 children. No single-child nodes.

Complete Binary Tree

All levels full except last; last level filled left → right. Used in heaps!

Perfect Binary Tree

All internals have 2 children; all leaves at same depth. Both full AND complete.

Type	Rule	Relationship
Full	Every node: 0 or 2 children	Not necessarily complete
Complete	All levels full; last left-filled	Used in heaps!
Perfect	All leaves same depth, all internals have 2	Both full AND complete

Perfect binary tree: exactly 2^h+1 − 1 nodes

Binary Tree Traversals

Traversal = visiting every node exactly once. Choose the order based on your goal.

Traversal	Order	Mnemonic	Use For
Preorder	Node, L, R	NLR	Copy/serialize
Inorder	L, Node, R	LNR	Sorted output (BST)
Postorder	L, R, Node	LRN	Delete / eval expr
Level-order	Top→bottom, L→R	BFS	Level-by-level

The "N" Position

The mnemonic tells you when you visit the node: before children (pre), between (in), or after (post).

Preorder Traversal (NLR)

Visit node FIRST, then recurse left, then recurse right.

preorder(node):
  if node == null: return
  visit(node)         // FIRST
  preorder(node.left)
  preorder(node.right)

Use Cases

Create a copy of the tree
Serialize a tree to string
Print a prefix expression

Inorder Traversal (LNR)

Recurse left, visit node IN THE MIDDLE, then recurse right.

inorder(node):
  if node == null: return
  inorder(node.left)
  visit(node)         // MIDDLE
  inorder(node.right)

Sorted Output from BST!

Inorder traversal of a BST visits nodes in ascending sorted order.

BST Example: inorder gives sorted output

Postorder Traversal (LRN)

Recurse left, recurse right, visit node LAST.

postorder(node):
  if node == null: return
  postorder(node.left)
  postorder(node.right)
  visit(node)         // LAST

Use Cases

Delete/free a tree (children before parent)
Evaluate expression trees
Calculate directory sizes

Root is always visited LAST

Must finish all descendants before processing a node. Think: "clean up children before yourself."

Level-Order Traversal (BFS)

Visit nodes level by level, left to right. Uses a queue.

levelOrder(root):
  queue Q
  Q.enqueue(root)
  while Q not empty:
    node = Q.dequeue()
    visit(node)
    enqueue children

Queue State:

Q = [ ]

Not Recursive!

The only standard traversal using a queue instead of recursion/stack.

Binary Search Tree (BST)

BST Property

For every node v:

All keys in left subtree < v's key
All keys in right subtree > v's key

Why BST?

Op	BST (balanced)	Array	Linked List
Search	O(log n)	O(log n)*	O(n)
Insert	O(log n)	O(n)	O(1)
Delete	O(log n)	O(n)	O(n)

* sorted array with binary search

Analogy: Phone Book

At each node: go left (smaller) or right (larger). Like binary search on a sorted array, stored as a tree.

BST Search

Compare target with current node. Go left if smaller, right if larger.

search(node, key):
  if node == null:
    return null       // not found
  if key == node.key:
    return node       // found!
  if key < node.key:
    return search(node.left, key)
  else:
    return search(node.right, key)

Each comparison eliminates half the tree

Like binary search on an array! Comparisons = depth of target node.

BST Insert

Search for the key. When you reach null, that's where the new node goes.

insert(node, key):
  if node == null:
    return new Node(key)  // leaf
  if key < node.key:
    node.left = insert(node.left, key)
  else if key > node.key:
    node.right = insert(node.right, key)
  return node

New nodes are always leaves!

Insert never modifies existing nodes — just creates a new leaf at the correct position.

Insertion Order Matters

Inserting 1,2,3,4,5 in order creates a skewed tree (linked list!). Different orders → different shapes.

BST Delete: Three Cases

Case 1: Leaf

Just remove it

Case 2: One Child

Replace with child

Case 3: Two Children

Find inorder successor

Difficulty increases: Case 1 (trivial) → Case 2 (bypass) → Case 3 (find successor, copy, delete) — next slide!

BST Delete: Two Children (Detail)

Delete 8: has two children, so find the inorder successor.

Why Inorder Successor?

The smallest value larger than the deleted node. It always has at most one child (right only), so deleting it is Case 1 or 2.

Alternative: Inorder Predecessor

Could also use the largest in the left subtree. Both work!

Challenge: Predict the Traversal

Given this tree, predict the output of each traversal.

Preorder (NLR):

Inorder (LNR):

Postorder (LRN):

BST Performance

Balanced: O(log n)

Insert: 8, 4, 12, 2, 6, 10, 14
height = 2 ≈ log₂(7)

Skewed: O(n)

Insert: 2, 4, 6, 8, 10, 12, 14
height = 6 = n − 1 (linked list!)

Try it: enter insertion order

BST Type	Height	Operations
Balanced	O(log n)	O(log n)
Skewed	O(n)	O(n)

Sorted input = worst case!

Self-balancing trees (AVL, Red-Black) prevent this.

Challenge: Fix the Bug

This BST insert function has a bug. Can you spot it?

void insert(Node node, int key) {
  if (node == null) {
    node = new Node(key);
    return;
  }
  if (key < node.key)
    insert(node.left, key);
  else if (key > node.key)
    insert(node.right, key);
}

Balanced BSTs (Preview)

Self-balancing trees guarantee O(log n) performance.

AVL Trees

Balance Factor = height(left) − height(right) must be in {−1, 0, +1}. When violated → rotate.

Red-Black Trees

Nodes are red or black. Rules ensure no path is more than 2× longer than any other.

AVL: Strictly balanced

Faster lookups, more rotations on insert/delete.

Red-Black: Loosely balanced

Fewer rotations, used by Java's TreeMap.

Coming Attraction

These will be covered in detail later. For now, know they exist and why: to prevent O(n) worst case.

Challenge: Pick the Right Structure

For each scenario, choose the best data structure.

1. Need O(1) average lookup by key

No ordering needed, just fast access.

2. Need range queries (all keys between 10–50)

Must support ordered iteration.

3. Represent HTML document structure

Nested elements with parent-child relationships.

4. Evaluate (3 + 4) * 2

Arithmetic with operator precedence.

Application: Expression Trees

Operators are internal nodes; operands are leaves. Evaluate with postorder!

Stack: [ ]

Expression: (3 + 4) × 2 = ?

Three Notations:

Traversal	Output	Notation
Preorder	`× + 3 4 2`	Prefix (Polish)
Inorder	`3 + 4 × 2`	Infix (needs parens!)
Postorder	`3 4 + 2 ×`	Postfix (RPN)

Infix is ambiguous without parentheses

Summary & Cheat Sheet

Traversals

Name	Order	Use For
Preorder	NLR	Copy/serialize
Inorder	LNR	Sorted output (BST)
Postorder	LRN	Delete / eval expr
Level-order	BFS	Level-by-level

BST Complexity

Type	Height	Ops
Balanced	O(log n)	O(log n)
Skewed	O(n)	O(n)

Key Takeaway

Trees organize data hierarchically. BSTs give O(log n) search/insert/delete — but only when balanced.

Quiz: Tree Fundamentals

Q1: Node Count

A perfect binary tree of height 3 has how many nodes?

7 8 15 16

Q2: Traversal

Which traversal gives sorted output from a BST?

Preorder Inorder Postorder Level-order

Q3: BST Delete

Deleting a node with two children requires finding the:

Parent node Inorder successor Deepest leaf Root node

Quiz: Build a BST

Insert these keys in order: 5, 3, 8, 1, 4, 7, 9. What is the tree's height?

Height of the resulting tree:

        Insert 5: root

        Insert 3: 3 < 5 → left of 5

        Insert 8: 8 > 5 → right of 5

        Insert 1: 1 < 5 → 1 < 3 → left of 3

        Insert 4: 4 < 5 → 4 > 3 → right of 3

        Insert 7: 7 > 5 → 7 < 8 → left of 8

        Insert 9: 9 > 5 → 9 > 8 → right of 8

Quiz: What Does This Print?

void mystery(Node n) {
  if (n == null) return;
  mystery(n.left);
  mystery(n.right);
  System.out.print(n.val + " ");
}

Called on this BST:

Output:

Trees

What Is a Tree?

Analogy: Family Tree

Key Property

Tree Terminology

Height of tree = max depth of any leaf

Formal Definition of a Tree

Recursive Definition

Key Property

Think Recursively

Tree ADT

Accessor Methods

depth() goes UP, height() goes DOWN

Depth and Height

Depth of a Node

Height of a Node

Height of Tree

Binary Trees

Properties of Binary Trees

Why Binary?

Left vs Right Matters!

Full vs Complete vs Perfect Binary Trees

Full Binary Tree

Complete Binary Tree

Perfect Binary Tree

Perfect binary tree: exactly 2h+1 − 1 nodes

Binary Tree Traversals

The "N" Position

Preorder Traversal (NLR)

Use Cases

Inorder Traversal (LNR)

Sorted Output from BST!

BST Example: inorder gives sorted output

Postorder Traversal (LRN)

Use Cases

Root is always visited LAST

Level-Order Traversal (BFS)

Queue State:

Not Recursive!

Binary Search Tree (BST)

BST Property

Why BST?

Analogy: Phone Book

BST Search

Each comparison eliminates half the tree

BST Insert

New nodes are always leaves!

Insertion Order Matters

BST Delete: Three Cases

Case 1: Leaf

Case 2: One Child

Case 3: Two Children

Difficulty increases: Case 1 (trivial) → Case 2 (bypass) → Case 3 (find successor, copy, delete) — next slide!

BST Delete: Two Children (Detail)

Why Inorder Successor?

Alternative: Inorder Predecessor

Challenge: Predict the Traversal

BST Performance

Balanced: O(log n)

Skewed: O(n)

Try it: enter insertion order

Sorted input = worst case!

Challenge: Fix the Bug

Balanced BSTs (Preview)

AVL Trees

Red-Black Trees

AVL: Strictly balanced

Red-Black: Loosely balanced

Coming Attraction

Challenge: Pick the Right Structure

1. Need O(1) average lookup by key

2. Need range queries (all keys between 10–50)

3. Represent HTML document structure

4. Evaluate (3 + 4) * 2

Application: Expression Trees

Expression: (3 + 4) × 2 = ?

Three Notations:

Infix is ambiguous without parentheses

Summary & Cheat Sheet

Traversals

Perfect binary tree: exactly 2^h+1 − 1 nodes