Chapter 08

Trees and Binary Search Trees

Trees organise data hierarchically. This chapter introduces tree terminology, binary-tree representations, recursive and iterative traversals, breadth-first search, common binary-tree problems, and binary search tree construction.

8.1What is a Tree?

Definition · Tree A tree is a hierarchical, non-linear data structure consisting of nodes. The top node is the root, and nodes are connected by edges.
Build the lecture tree, one relationship at a time
Each child has exactly one parent, and the structure contains no cycles.
general tree
Start with the root node.

8.2Tree Terminology

Root

The topmost node in a tree.

Edge

A connection between two nodes.

Child

A node derived from a parent.

Parent

A node with one or more children.

Leaf

A node with no children.

From the lecture tree Node 1 is the root. Node 4 is a child of node 1 and the parent of nodes 8 and 9. Nodes 5, 6, 8, 9, and 10 are leaves.

8.3Types of Trees

Binary Tree

Each node has at most two children: zero, one, or two.

Not a Binary Tree

Node 1 has three children, so the binary-tree rule is violated.

Full Binary Tree

Every node has either zero or two children.

Complete Binary Tree

Every level is full except possibly the last, which fills from left to right.

Binary Search Tree A binary tree in which every key in the left subtree is less than the root key, and every key in the right subtree is greater than the root key.
AVL Tree
A self-balancing BST.
Heap
A tree with a maximum or minimum property.
B-Tree
A balanced tree designed for disk storage.

8.4Binary Tree Representation

Array representation

For a node at index i:

  • left child = 2i + 1
  • right child = 2i + 2
  • parent = ⌊(i − 1) / 2⌋, for i > 0

Linked representation

Each node stores data plus pointers to its left and right children.

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

class Tree:
    def __init__(self):
        self.root = None

8.5Binary Tree Traversals

TraversalOrderLecture sequence
InorderLeft, Root, Right4 → 2 → 5 → 1 → 6 → 3 → 7
PreorderRoot, Left, Right1 → 2 → 4 → 5 → 3 → 6 → 7
PostorderLeft, Right, Root4 → 5 → 2 → 6 → 7 → 3 → 1
Traversal laboratory
Each recursive call pushes an activation record; every return pops the top frame.
not visited current node visited

Program call stack

CALL STACK · BOTTOM
EMPTY · no active call
Choose Play or Step.
Traversal complexity Every traversal visits each of the n nodes once, so its time is O(n). Recursive traversal uses O(h) call-stack space, where h is the tree height: O(log n) for a balanced tree and O(n) for a skewed tree.

8.6Recursive Traversals

Inorder

InorderTraversal(node):
    if node is not NULL:
        InorderTraversal(node.left)
        Visit(node)
        InorderTraversal(node.right)

Preorder

PreorderTraversal(node):
    if node is not NULL:
        Visit(node)
        PreorderTraversal(node.left)
        PreorderTraversal(node.right)

Postorder

PostorderTraversal(node):
    if node is not NULL:
        PostorderTraversal(node.left)
        PostorderTraversal(node.right)
        Visit(node)
Applications from the slides Preorder can transfer a directory structure. Postorder is useful when deleting an entire tree because every child is processed before its parent.

8.7Iterative Traversals with Stacks

Explicit-stack traversal laboratory
Unlike a call frame, each stack cell stores only a pending node reference.

Explicit stack S

STACK S · BOTTOM
INITIALIZE · stack S is empty
Initialize the traversal.
show the iterative algorithms

Iterative inorder

IterativeInorderTraversal(root):
    Initialize an empty stack
    current = root
    while current is not NULL or stack is not empty:
        while current is not NULL:
            Push current to stack
            current = current.left
        current = Pop from stack
        Visit(current)
        current = current.right

Iterative preorder using one stack

IterativePreorder(root):
    if root == NULL: return
    Push root into stack S
    while S is not empty:
        node = S.pop()
        Visit(node)
        if node.right != NULL: Push node.right
        if node.left != NULL: Push node.left

Iterative postorder using two stacks

IterativePostorder(root):
    if root == NULL: return
    Push root into S1
    while S1 is not empty:
        node = S1.pop()
        Push node into S2
        if node.left != NULL: Push node.left into S1
        if node.right != NULL: Push node.right into S1
    while S2 is not empty:
        Visit(S2.pop())
Single-stack variant Iterative postorder can also be implemented with one stack; the two-stack version above makes the processing order easier to see.

8.8Level-Order Traversal — BFS

LEVEL-ORDER(root):
1. Initialize an empty queue
2. Enqueue the root node
3. Repeat until the queue is empty:
   a. Dequeue a node and process it
   b. Enqueue its left child, if it exists
   c. Enqueue its right child, if it exists
Breadth-first search with a live queue
Nodes are processed level by level: 1, 2, 3, 4, 5, 6, 7.

Queue · front to rear

Output

Initialize an empty queue.

8.9Problems on Binary Trees

Size

Count the number of nodes.

Search

Find a given key.

Minimum / Maximum

Find the smallest and largest values.

Delete the tree

Process children before their parent.

Height

Find the longest root-to-leaf path.

Deepest node

Find the node at maximum depth.

Same structure

Compare two binary-tree shapes.

Sum

Add every element in the tree.

Height(root):
1. if root == NULL: return 0
2. left_height = Height(root.left)
3. right_height = Height(root.right)
4. return 1 + max(left_height, right_height)
SumTree(root):
1. if root == NULL: return 0
2. left_sum = SumTree(root.left)
3. right_sum = SumTree(root.right)
4. return root.data + left_sum + right_sum

8.10Reconstructing a Tree from Traversals

Inorder
D B E A F C
Preorder
A B D E C F
Build the exact tree, one split at a time
Preorder identifies each root; inorder separates its left and right subtrees.
Postorder: —
The first preorder element A is the root.
Identification rule With distinct node values, inorder paired with preorder or postorder uniquely identifies the tree. Without inorder, the tree is not uniquely determined in general.

8.11Binary Search Tree — Searching

Definition · BST Every value in the left subtree is smaller than the root value, and every value in the right subtree is greater. 
SEARCH(root, key):
1. if root == NULL: return NULL
2. if root.data == key: return root
3. if key < root.data:
       return SEARCH(root.left, key)
4. return SEARCH(root.right, key)
Follow one BST search path
Every comparison discards an entire subtree.
Begin at the root.
Time complexity Searching takes O(log n) in a balanced BST, but can take O(n) in a skewed BST.

8.12BST Construction

Insert(node, key):
1. if node is NULL:
       return a new node containing key
2. if key < node.data:
       node.left = Insert(node.left, key)
3. else if key > node.data:
       node.right = Insert(node.right, key)
4. return node
Insert each value and watch the tree grow
Compare average-order insertion with sorted-order insertion.
The tree is empty.
Average construction For a reasonably balanced insertion order, inserting n elements takes O(n log n).
Worst construction Sorted input produces a right-skewed BST and takes O(n²).
show balanced construction from a sorted array 
build_tree(arr):
    if not arr: return None
    mid = len(arr) // 2
    node = Node(arr[mid])
    node.left = build_tree(arr[:mid])
    node.right = build_tree(arr[mid + 1:])
    return node

8.13Questions and Self Study

Worst time to find the minimum in a right-skewed BST?
show answer

O(1) The root has no left child, so it is already the minimum.

Worst time to find the minimum in a left-skewed BST?
show answer

O(n) Follow the left pointer through every node.

Self study Delete an element from a binary search tree.