Chapter 3.11: Binary Trees

Binary trees are the foundation of some of the most important data structures in competitive programming — from Binary Search Trees (BST) to Segment Trees to Heaps. Understanding them deeply will make graph algorithms, DP on trees, and USACO Gold problems significantly more approachable.

3.11.1 Binary Tree Fundamentals

A binary tree is a hierarchical data structure where:

• Each node has at most 2 children: a left child and a right child
• There is exactly one root node (no parent)
• Each non-root node has exactly one parent

Visual Example

In this tree:

• Height = 2 (longest root-to-leaf path: A → B → D)
• Root = A, Leaves = D, E, F
• B is parent of D and E; D is left child of B, E is right child of B

C++ Node Definition

Throughout this chapter, we use a consistent struct TreeNode:

// Solution: Basic Binary Tree Node
#include <bits/stdc++.h>
using namespace std;

struct TreeNode {
    int val;
    TreeNode* left;
    TreeNode* right;
    
    // Constructor: initialize with value, no children
    TreeNode(int v) : val(v), left(nullptr), right(nullptr) {}
};

💡 Why raw pointers? In competitive programming, we often manage memory manually for speed. nullptr (C++11) is always safer than uninitialized pointers — always initialize left = right = nullptr.

3.11.2 Binary Search Trees (BST)

A Binary Search Tree is a binary tree with a crucial ordering property:

BST Property: For every node v:

• All values in the left subtree are strictly less than v.val
• All values in the right subtree are strictly greater than v.val

       [5]          ← valid BST
      /    \
    [3]    [8]
   /   \   /  \
  [1] [4] [7] [10]

  left of 5 = {1, 3, 4} — all < 5  ✓
  right of 5 = {7, 8, 10} — all > 5  ✓

3.11.2.1 BST Search

// Solution: BST Search — O(log N) average, O(N) worst case
// Returns pointer to node with value 'target', or nullptr if not found
TreeNode* search(TreeNode* root, int target) {
    // Base case: empty tree or found the target
    if (root == nullptr || root->val == target) {
        return root;
    }
    // BST property: go left if target is smaller
    if (target < root->val) {
        return search(root->left, target);
    }
    // Go right if target is larger
    return search(root->right, target);
}

Iterative version (avoids stack overflow for large trees):

// Solution: BST Search Iterative
TreeNode* searchIterative(TreeNode* root, int target) {
    while (root != nullptr) {
        if (target == root->val) return root;       // found
        else if (target < root->val) root = root->left;   // go left
        else root = root->right;                     // go right
    }
    return nullptr;  // not found
}

3.11.2.2 BST Insert

// Solution: BST Insert — O(log N) average
// Returns the (potentially new) root of the subtree
TreeNode* insert(TreeNode* root, int val) {
    // If we've reached a null spot, create the new node here
    if (root == nullptr) {
        return new TreeNode(val);
    }
    if (val < root->val) {
        root->left = insert(root->left, val);   // recurse left
    } else if (val > root->val) {
        root->right = insert(root->right, val); // recurse right
    }
    // val == root->val: duplicate, ignore (or handle as needed)
    return root;
}

// Usage:
// TreeNode* root = nullptr;
// root = insert(root, 5);
// root = insert(root, 3);
// root = insert(root, 8);

3.11.2.3 BST Delete

Deletion is the trickiest BST operation. There are 3 cases:

1. Node has no children (leaf): simply delete it
2. Node has one child: replace node with its child
3. Node has two children: replace with inorder successor (smallest in right subtree), then delete the successor

// Solution: BST Delete — O(log N) average
// Helper: find minimum node in a subtree
TreeNode* findMin(TreeNode* node) {
    while (node->left != nullptr) node = node->left;
    return node;
}

// Delete node with value 'val' from tree rooted at 'root'
TreeNode* deleteNode(TreeNode* root, int val) {
    if (root == nullptr) return nullptr;  // value not found
    
    if (val < root->val) {
        // Case: target is in left subtree
        root->left = deleteNode(root->left, val);
    } else if (val > root->val) {
        // Case: target is in right subtree
        root->right = deleteNode(root->right, val);
    } else {
        // Found the node to delete!
        
        // Case 1: No children (leaf)
        if (root->left == nullptr && root->right == nullptr) {
            delete root;
            return nullptr;
        }
        // Case 2a: Only right child
        else if (root->left == nullptr) {
            TreeNode* temp = root->right;
            delete root;
            return temp;
        }
        // Case 2b: Only left child
        else if (root->right == nullptr) {
            TreeNode* temp = root->left;
            delete root;
            return temp;
        }
        // Case 3: Two children — replace with inorder successor
        else {
            TreeNode* successor = findMin(root->right);  // smallest in right subtree
            root->val = successor->val;                  // copy successor's value
            root->right = deleteNode(root->right, successor->val);  // delete successor
        }
    }
    return root;
}

3.11.2.4 BST Degeneration Problem

⚠️ Critical Issue: If you insert values in sorted order (1, 2, 3, 4, 5...), the BST becomes a linked list:

[1]
  \
  [2]
    \
    [3]        ← This is O(N) per operation, not O(log N)!
      \
      [4]
        \
        [5]

This is why balanced BSTs (AVL trees, Red-Black trees) exist. In C++, std::set and std::map are implemented as Red-Black trees — always O(log N).

3.11.3 Tree Traversals

Traversal = visiting every node exactly once. There are 4 fundamental traversals:

3.11.3.1 Preorder Traversal

// Solution: Preorder Traversal — O(N) time, O(H) space (H = height)
// Visit order: Root, Left subtree, Right subtree
void preorder(TreeNode* root) {
    if (root == nullptr) return;   // base case
    cout << root->val << " ";      // process ROOT first
    preorder(root->left);          // then left subtree
    preorder(root->right);         // then right subtree
}

// For the tree:    [5]
//                 /    \
//               [3]    [8]
//              /   \
//            [1]   [4]
// Preorder: 5 3 1 4 8

Iterative Preorder (using stack):

// Solution: Preorder Iterative
void preorderIterative(TreeNode* root) {
    if (root == nullptr) return;
    stack<TreeNode*> stk;
    stk.push(root);
    
    while (!stk.empty()) {
        TreeNode* node = stk.top(); stk.pop();
        cout << node->val << " ";    // process current
        
        // Push RIGHT first (so LEFT is processed first — LIFO!)
        if (node->right) stk.push(node->right);
        if (node->left)  stk.push(node->left);
    }
}

3.11.3.2 Inorder Traversal

// Solution: Inorder Traversal — O(N) time
// Visit order: Left subtree, Root, Right subtree
// KEY PROPERTY: Inorder traversal of a BST gives SORTED output!
void inorder(TreeNode* root) {
    if (root == nullptr) return;
    inorder(root->left);           // left subtree first
    cout << root->val << " ";      // then ROOT
    inorder(root->right);          // then right subtree
}

// For BST with values {1, 3, 4, 5, 8}:
// Inorder: 1 3 4 5 8  ← sorted! This is the most important BST property

🔑 Key Insight: Inorder traversal of any BST always produces a sorted sequence. This is why std::set can be iterated in sorted order — it uses inorder traversal internally.

Iterative Inorder (slightly trickier):

// Solution: Inorder Iterative
void inorderIterative(TreeNode* root) {
    stack<TreeNode*> stk;
    TreeNode* curr = root;
    
    while (curr != nullptr || !stk.empty()) {
        // Go as far left as possible
        while (curr != nullptr) {
            stk.push(curr);
            curr = curr->left;
        }
        // Process the leftmost unprocessed node
        curr = stk.top(); stk.pop();
        cout << curr->val << " ";
        
        // Move to right subtree
        curr = curr->right;
    }
}

3.11.3.3 Postorder Traversal

// Solution: Postorder Traversal — O(N) time
// Visit order: Left subtree, Right subtree, Root
// Used for: deleting trees, evaluating expression trees
void postorder(TreeNode* root) {
    if (root == nullptr) return;
    postorder(root->left);         // left subtree first
    postorder(root->right);        // then right subtree
    cout << root->val << " ";      // ROOT last
}

// For BST [1, 3, 4, 5, 8]:
// Postorder: 1 4 3 8 5  (root 5 is always last)

// ── Memory cleanup using postorder ──
void deleteTree(TreeNode* root) {
    if (root == nullptr) return;
    deleteTree(root->left);   // delete left first
    deleteTree(root->right);  // then right
    delete root;              // then this node (safe: children already deleted)
}

3.11.3.4 Level-Order Traversal (BFS)

// Solution: Level-Order Traversal (BFS) — O(N) time, O(W) space (W = max width)
// Uses a queue: process nodes level by level
void levelOrder(TreeNode* root) {
    if (root == nullptr) return;
    
    queue<TreeNode*> q;
    q.push(root);
    
    while (!q.empty()) {
        int levelSize = q.size();  // number of nodes at current level
        
        for (int i = 0; i < levelSize; i++) {
            TreeNode* node = q.front(); q.pop();
            cout << node->val << " ";
            
            if (node->left)  q.push(node->left);
            if (node->right) q.push(node->right);
        }
        cout << "\n";  // newline between levels
    }
}

// For the BST [5, 3, 8, 1, 4]:
// Level 0: 5
// Level 1: 3 8
// Level 2: 1 4

Traversal Summary Table

Tree:           [5]
               /    \
             [3]    [8]
            /   \   /
          [1]  [4] [7]

Preorder:   5 3 1 4 8 7
Inorder:    1 3 4 5 7 8    ← sorted!
Postorder:  1 4 3 7 8 5
Level-order: 5 | 3 8 | 1 4 7

3.11.4 Tree Height and Balance

3.11.4.1 Computing Tree Height

// Solution: Tree Height — O(N) time, O(H) space for recursion stack
// Height = length of longest root-to-leaf path
// Convention: height of null tree = -1, leaf node height = 0
int height(TreeNode* root) {
    if (root == nullptr) return -1;  // empty subtree has height -1
    
    int leftHeight  = height(root->left);   // height of left subtree
    int rightHeight = height(root->right);  // height of right subtree
    
    return 1 + max(leftHeight, rightHeight);  // +1 for current node
}
// Time: O(N) — visit every node exactly once
// Space: O(H) — recursion stack depth = tree height

// Alternative: some define height as number of nodes on longest path
// Then: leaf has height 1, and empty tree has height 0
// Be careful about which convention your problem uses!

3.11.4.2 Checking Balance

A balanced binary tree requires that for every node, the heights of its left and right subtrees differ by at most 1.

// Solution: Check Balanced BST — O(N) time
// Returns -1 if unbalanced, otherwise returns the height of subtree
int checkBalanced(TreeNode* root) {
    if (root == nullptr) return 0;  // empty is balanced, height 0
    
    int leftH = checkBalanced(root->left);
    if (leftH == -1) return -1;     // left subtree is unbalanced
    
    int rightH = checkBalanced(root->right);
    if (rightH == -1) return -1;    // right subtree is unbalanced
    
    // Check balance at current node: heights can differ by at most 1
    if (abs(leftH - rightH) > 1) return -1;  // unbalanced!
    
    return 1 + max(leftH, rightH);   // return height if balanced
}

bool isBalanced(TreeNode* root) {
    return checkBalanced(root) != -1;
}

3.11.4.3 Counting Nodes

// Solution: Count Nodes — O(N)
int countNodes(TreeNode* root) {
    if (root == nullptr) return 0;
    return 1 + countNodes(root->left) + countNodes(root->right);
}

// Count leaves specifically
int countLeaves(TreeNode* root) {
    if (root == nullptr) return 0;
    if (root->left == nullptr && root->right == nullptr) return 1;  // leaf!
    return countLeaves(root->left) + countLeaves(root->right);
}

3.11.5 Lowest Common Ancestor (LCA) — Brute Force

The LCA of two nodes u and v in a rooted tree is the deepest node that is an ancestor of both.

          [1]
         /    \
       [2]    [3]
      /   \      \
    [4]   [5]   [6]
   /
  [7]

LCA(4, 5) = 2     (both 4 and 5 are descendants of 2)
LCA(4, 6) = 1     (deepest common ancestor is the root 1)
LCA(2, 4) = 2     (node 2 is ancestor of 4 and ancestor of itself)

O(N) Brute Force LCA

// Solution: LCA Brute Force — O(N) per query
// Strategy: find path from root to each node, then find last common node

// Step 1: Find path from root to target node
bool findPath(TreeNode* root, int target, vector<int>& path) {
    if (root == nullptr) return false;
    
    path.push_back(root->val);  // add current node to path
    
    if (root->val == target) return true;  // found target!
    
    // Try left then right
    if (findPath(root->left, target, path)) return true;
    if (findPath(root->right, target, path)) return true;
    
    path.pop_back();  // backtrack: target not in this subtree
    return false;
}

// Step 2: Find LCA using two paths
int lca(TreeNode* root, int u, int v) {
    vector<int> pathU, pathV;
    
    findPath(root, u, pathU);   // path from root to u
    findPath(root, v, pathV);   // path from root to v
    
    // Find last common node in both paths
    int result = root->val;
    int minLen = min(pathU.size(), pathV.size());
    
    for (int i = 0; i < minLen; i++) {
        if (pathU[i] == pathV[i]) {
            result = pathU[i];  // still common
        } else {
            break;  // diverged
        }
    }
    return result;
}

💡 USACO Note: For USACO Silver problems, the O(N) brute force LCA is NOT always sufficient. With N ≤ 10^5 nodes and Q ≤ 10^5 queries, the total is O(NQ) = O(10^10) — too slow. Use it only when N, Q ≤ 5000. Chapter 5.3 covers O(log N) LCA with binary lifting for harder problems.

3.11.6 Complete BST Implementation

Here's a complete, contest-ready BST with all operations:

// Solution: Complete BST Implementation
#include <bits/stdc++.h>
using namespace std;

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

struct BST {
    TreeNode* root;
    BST() : root(nullptr) {}
    
    // ── Insert ──
    TreeNode* _insert(TreeNode* node, int val) {
        if (!node) return new TreeNode(val);
        if (val < node->val) node->left  = _insert(node->left,  val);
        else if (val > node->val) node->right = _insert(node->right, val);
        return node;
    }
    void insert(int val) { root = _insert(root, val); }
    
    // ── Search ──
    bool search(int val) {
        TreeNode* curr = root;
        while (curr) {
            if (val == curr->val) return true;
            curr = (val < curr->val) ? curr->left : curr->right;
        }
        return false;
    }
    
    // ── Inorder (sorted output) ──
    void _inorder(TreeNode* node, vector<int>& result) {
        if (!node) return;
        _inorder(node->left, result);
        result.push_back(node->val);
        _inorder(node->right, result);
    }
    vector<int> getSorted() {
        vector<int> result;
        _inorder(root, result);
        return result;
    }
    
    // ── Height ──
    int _height(TreeNode* node) {
        if (!node) return -1;
        return 1 + max(_height(node->left), _height(node->right));
    }
    int height() { return _height(root); }
};

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    
    BST bst;
    vector<int> vals = {5, 3, 8, 1, 4, 7, 10};
    for (int v : vals) bst.insert(v);
    
    cout << "Sorted: ";
    for (int v : bst.getSorted()) cout << v << " ";
    cout << "\n";
    // Output: 1 3 4 5 7 8 10
    
    cout << "Height: " << bst.height() << "\n";  // 2
    cout << "Search 4: " << bst.search(4) << "\n";  // 1 (true)
    cout << "Search 6: " << bst.search(6) << "\n";  // 0 (false)
    
    return 0;
}

3.11.7 USACO-Style Practice Problem

Problem: "Cow Family Tree" (USACO Bronze Style)

Problem Statement:

Farmer John has N cows numbered 1 to N. Cow 1 is the ancestor of all cows (the "root"). For each cow i (2 ≤ i ≤ N), its parent is cow parent[i]. The depth of a cow is defined as the number of edges from the root (cow 1) to that cow (so cow 1 has depth 0).

Given the tree and M queries, each asking "what is the depth of cow x?", answer all queries.

Input:

• Line 1: N, M (1 ≤ N, M ≤ 100,000)
• Lines 2 to N: each line contains i parent[i]
• Next M lines: each contains a single integer x

Output: For each query, print the depth of cow x.

Sample Input:

5 3
2 1
3 1
4 2
5 3
4
5
1

Sample Output:

2
2
0

• Cow 4's path: 4→2→1, depth = 2
• Cow 5's path: 5→3→1, depth = 2
• Cow 1: root, depth = 0

Solution Approach: Use DFS/BFS to compute depth of each node.

// Solution: Cow Family Tree — Depth Query
#include <bits/stdc++.h>
using namespace std;

const int MAXN = 100005;
vector<int> children[MAXN];  // adjacency list: children[i] = list of i's children
int depth[MAXN];             // depth[i] = depth of node i

// DFS to compute depths
void dfs(int node, int d) {
    depth[node] = d;
    for (int child : children[node]) {
        dfs(child, d + 1);  // children have depth+1
    }
}

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    
    int n, m;
    cin >> n >> m;
    
    for (int i = 2; i <= n; i++) {
        int par;
        cin >> par;
        children[par].push_back(i);  // par is parent of i
    }
    
    dfs(1, 0);  // start DFS from root (cow 1) at depth 0
    
    while (m--) {
        int x;
        cin >> x;
        cout << depth[x] << "\n";
    }
    
    return 0;
}
// Time: O(N + M)
// Space: O(N)

// Instead of depth, compute path sum (sum of node values on path to root)
int pathSum[MAXN];  // pathSum[i] = sum of values from root to i
int nodeVal[MAXN];  // nodeVal[i] = value of node i

void dfs(int node, int cumSum) {
    pathSum[node] = cumSum + nodeVal[node];
    for (int child : children[node]) {
        dfs(child, pathSum[node]);
    }
}
// Query: just return pathSum[x] in O(1)

3.11.8 Building a Tree from Traversals

A classic problem: given preorder and inorder traversals, reconstruct the original tree.

Key insight:

• The first element of preorder is always the root
• In the inorder array, the root splits it into left and right subtrees

// Solution: Reconstruct Tree from Preorder + Inorder — O(N^2) naive
TreeNode* build(vector<int>& pre, int preL, int preR,
                vector<int>& in,  int inL,  int inR) {
    if (preL > preR) return nullptr;
    
    int rootVal = pre[preL];  // first preorder element = root
    TreeNode* root = new TreeNode(rootVal);
    
    // Find root in inorder array
    int rootIdx = inL;
    while (in[rootIdx] != rootVal) rootIdx++;
    
    int leftSize = rootIdx - inL;  // number of nodes in left subtree
    
    // Recursively build left and right subtrees
    root->left  = build(pre, preL+1, preL+leftSize, in, inL, rootIdx-1);
    root->right = build(pre, preL+leftSize+1, preR, in, rootIdx+1, inR);
    
    return root;
}

TreeNode* buildTree(vector<int>& preorder, vector<int>& inorder) {
    int n = preorder.size();
    return build(preorder, 0, n-1, inorder, 0, n-1);
}

⚠️ Common Mistakes

// BAD: No null check!
void inorder(TreeNode* root) {
    inorder(root->left);  // CRASH if root is null
    cout << root->val;
    inorder(root->right);
}

// GOOD: Base case first
void inorder(TreeNode* root) {
    if (root == nullptr) return;  // ← critical!
    inorder(root->left);
    cout << root->val;
    inorder(root->right);
}

// BAD: Recursive DFS on a 10^5 node
// degenerate tree (skewed) = 10^5 recursion depth
// Default stack ~ 8MB = overflow around 10^4-10^5!
void dfsRecursive(TreeNode* root) {
    if (!root) return;
    process(root);
    dfsRecursive(root->left);
    dfsRecursive(root->right);
}

// GOOD: Use explicit stack for large trees
void dfsIterative(TreeNode* root) {
    stack<TreeNode*> stk;
    if (root) stk.push(root);
    while (!stk.empty()) {
        TreeNode* node = stk.top(); stk.pop();
        process(node);
        if (node->right) stk.push(node->right);
        if (node->left)  stk.push(node->left);
    }
}

Top 5 BST/Tree Bugs

1. Forgetting nullptr base case — causes segfault immediately
2. Not returning the (potentially new) root from insert/delete — tree structure broken
3. Stack overflow — use iterative traversal for N > 10^5
4. Memory leak — always delete nodes you remove (or use smart pointers)
5. Using unbalanced BST when STL set would work — use std::set in contests

Chapter Summary

📌 Key Takeaways

❓ FAQ

Q1: When should I use BST vs std::set?

A: In competitive programming, almost always use std::set. std::set is backed by a red-black tree (balanced BST), guaranteeing O(log N); a hand-written BST may degenerate to O(N). Only consider writing your own BST when you need custom BST behavior (e.g., tracking subtree sizes for "K-th largest" queries), or use __gnu_pbds::tree (Policy-Based Data Structure).

Q2: What is the relationship between Segment Tree and BST?

A: Segment Tree (Chapter 3.9) is a complete binary tree, but not a BST—nodes store range aggregate values (like range sums), not ordered keys. Both are binary trees with similar structure, but completely different purposes. Understanding BST pointer/recursion operations makes Segment Tree code easier to understand.

Q3: Which traversal—preorder/inorder/postorder—is most common in contests?

A: Inorder is most important—it outputs the BST's sorted sequence. Postorder is common for tree DP (compute children before parent). Level-order (BFS) is used when processing by level. Preorder is less common, but useful for serializing/deserializing trees.

Q4: Which is better, recursive or iterative implementation?

A: Recursive code is concise and easy to understand (preferred in contests). But when N ≥ 10^5 and the tree may degenerate, recursion risks stack overflow (default stack ~8MB, supports ~10^4~10^5 levels). USACO problems usually have non-degenerate trees, so recursion is usually fine; but if unsure, iterative is safer.

Q5: How important is LCA in competitive programming?

A: Very important! LCA is the foundation of tree DP and path queries. It appears occasionally in USACO Silver and is almost always tested in USACO Gold. The O(N) brute-force LCA learned here handles N ≤ 5000. The O(log N) Binary Lifting LCA is covered in detail in Chapter 5.3 (Trees & Special Graphs).

🔗 Connections to Other Chapters

• Chapter 2.3 (Functions & Arrays): foundation of recursion—binary tree traversal is a perfect application of recursion
• Chapter 3.8 (Maps & Sets): std::set / std::map are backed by balanced BST; understanding BST helps you use them better
• Chapter 3.9 (Segment Trees): Segment Tree is a complete binary tree; the recursive structure of build/query/update is identical to BST traversal
• Chapter 5.2 (Graph Algorithms): trees are special undirected graphs (connected, acyclic); all tree algorithms are special cases of graph algorithms
• Chapter 5.3 (Trees & Special Graphs): LCA Binary Lifting, Euler Tour—built directly on this chapter's foundation

Practice Problems

Problem 3.11.1 — BST Validator 🟢 Easy Given a binary tree (not necessarily a BST), determine if it satisfies the BST property (all left subtree values < node < all right subtree values for every node).

Problem 3.11.2 — BST Inorder K-th Smallest 🟢 Easy Given a BST, find the K-th smallest element.

Problem 3.11.3 — Tree Diameter 🟡 Medium Given a binary tree (not a BST), find the longest path between any two nodes (the diameter). The path does not need to pass through the root.

Problem 3.11.4 — Flatten BST to Sorted Array (USACO Style) 🟡 Medium You are given a BST with N nodes. N cows are each assigned a "score" (the node value). Find the median cow score (the ⌈N/2⌉-th smallest value).

Problem 3.11.5 — Maximum Path Sum 🔴 Hard Given a binary tree where nodes can have negative values, find the path (between any two nodes) with the maximum sum. A path can go up and down through the tree.

End of Chapter 3.11 — Next: Chapter 4.1: Greedy Fundamentals