19 Binary Trees — Introduction

20 Binary Trees — Introduction

Week 9, Session 1. CSS 342.

20.1 Warmup

Maximum Depth of Binary Tree (#104). Given a binary tree, return its depth.

struct TreeNode {
  int val;
  TreeNode* left;
  TreeNode* right;
  TreeNode(int v) : val(v), left(nullptr), right(nullptr) {}
};

class Solution {
 public:
  int maxDepth(TreeNode* root) {
    if (root == nullptr) return 0;
    return 1 + max(maxDepth(root->left), maxDepth(root->right));
  }
};

Three lines. One of them is the base case. Recursion on trees is clean — that is one of the chapter’s main points.

20.2 Learning objectives

Define and draw a binary tree using correct terminology.
Implement in-order, pre-order, and post-order traversals recursively.
Implement BST insert and search recursively.
Verify that a tree satisfies the BST property.
Explain why a degenerate BST degrades to O(n).

20.3 Terminology

            50            <- root
           /   \
         30     70
        /  \   /  \
       20  40 60  80    <- leaves (here, all of them)

Root: the top node.
Parent / child: 50 is the parent of 30 and 70; 30 is the parent of 20 and 40.
Sibling: 30 and 70.
Leaf: a node with no children.
Height of a node: the number of edges on the longest path to a leaf. Leaves have height 0. The root above has height 2.
Depth of a node: number of edges from the root. Root has depth 0.
Subtree: a node plus all its descendants.

20.4 TreeNode

struct TreeNode {
  int data;
  TreeNode* left;
  TreeNode* right;
  TreeNode(int v) : data(v), left(nullptr), right(nullptr) {}
};

Two children instead of one. Otherwise identical to a linked list node.

20.5 Traversals

There are three classic recursive traversals.

void inOrder(TreeNode* node) {
  if (node == nullptr) return;
  inOrder(node->left);
  cout << node->data << " ";
  inOrder(node->right);
}

void preOrder(TreeNode* node) {
  if (node == nullptr) return;
  cout << node->data << " ";
  preOrder(node->left);
  preOrder(node->right);
}

void postOrder(TreeNode* node) {
  if (node == nullptr) return;
  postOrder(node->left);
  postOrder(node->right);
  cout << node->data << " ";
}

The three are identical except for when you print: before, between, or after the recursive calls. The names tell you where the visit happens relative to the children.

On the example tree:

In-order: 20 30 40 50 60 70 80
Pre-order: 50 30 20 40 70 60 80
Post-order: 20 40 30 60 80 70 50

The in-order traversal of a binary search tree produces sorted output. That is the killer property. We will use it to sanity-check every BST we build.

20.6 The BST property

A binary search tree is a binary tree with one invariant:

For every node, all values in its left subtree are less than its value, and all values in its right subtree are greater.

(Variant for duplicates: ≤ on one side. Pick a convention. We’ll say “no duplicates” in this book unless stated.)

20.7 Insert

void insert(TreeNode*& root, int value) {
  if (root == nullptr) {
    root = new TreeNode(value);
    return;
  }
  if (value < root->data) insert(root->left, value);
  else if (value > root->data) insert(root->right, value);
  // duplicate: ignore
}

The TreeNode*& is the same trick from linked lists: we want to modify the pointer the caller holds when we drop in a new node at the empty slot.

TreeNode* root = nullptr;
insert(root, 50);
insert(root, 30);
insert(root, 70);
insert(root, 20);
insert(root, 40);
inOrder(root);     // 20 30 40 50 70  ← sorted!

20.8 Search

bool search(TreeNode* root, int value) {
  if (root == nullptr) return false;
  if (value == root->data) return true;
  if (value < root->data) return search(root->left, value);
  return search(root->right, value);
}

At each step we discard half the tree. If the tree is balanced, this is O(log n).

20.9 Height — for free with recursion

int height(TreeNode* node) {
  if (node == nullptr) return -1;     // empty tree has height -1
  return 1 + max(height(node->left), height(node->right));
}

A common convention: empty tree has height -1, a single node has height 0. (Other books use 0 / 1. Read the prompt carefully on exams.)

20.10 The degenerate case

Insert {1, 2, 3, 4, 5} in order. What does the BST look like?

A straight right-spine. Height = n − 1. Search is O(n). Insert is O(n). The tree has degenerated into a linked list.

This is why CSS 343 spends a whole lecture on balanced trees (AVL, red-black) — they guarantee O(log n) by rotating to prevent this degeneracy.

20.11 Try it

Write a function countNodes(TreeNode* root) that returns the number of nodes in the tree. Two-line recursion.

int countNodes(TreeNode* node) {
  if (node == nullptr) return 0;
  return 1 + countNodes(node->left) + countNodes(node->right);
}

Now: what is the complexity? Each node is visited exactly once. O(n).

20.12 Self-check

1. In-order traversal of a BST produces:

a. The same as pre-order.
b. The elements in sorted order.
c. Random order.
d. The reverse of post-order.

b. The BST property guarantees left < node < right; in-order visits in that exact sequence.

2. Inserting {1, 2, 3, 4, 5} in order into a plain BST produces:

a. A balanced tree of height 2.
b. A tree shaped like a heap.
c. An error — duplicates.
d. A right-spine degenerate tree of height 4.

d. Every new element is larger; goes right; tree becomes a linked list. Balanced trees fix this.

20.13 Challenges

Validate Binary Search Tree (#98) — recursive with bounds.
Same Tree (#100) — two simultaneous traversals.
Invert Binary Tree (#226) — swap children at every node.
Path Sum (#112) — accumulator recursion.

20.14 Where this fits

The basic vocabulary of trees. Next chapter pushes harder — BST delete (the surprisingly hard case), advanced recursion patterns, and a preview of what 343 will do with all this.

You are here	Coming up
Tree terminology, traversals, BST insert / search, degeneration	Chapter 18: advanced recursion and tree problems