Project 8: Binary Tree and BST Complete Implementation

Implement binary trees and binary search trees with full traversal support.

Quick Reference

Attribute Value
Difficulty Level 3: Advanced
Time Estimate 2 weeks
Language C (Alternatives: Python, Java, Rust)
Prerequisites Projects 4-6, recursion comfort
Key Topics Trees, BST operations, traversals

1. Learning Objectives

By completing this project, you will:

  1. Implement binary tree nodes and traversal algorithms.
  2. Implement BST insert, search, and delete.
  3. Visualize tree structure in the terminal.
  4. Analyze time complexity in balanced vs skewed trees.

2. Theoretical Foundation

2.1 Core Concepts

  • Binary tree: Each node has up to two children.
  • BST invariant: Left subtree < node < right subtree.
  • Traversals: Preorder, inorder, postorder, level-order.
  • Balance: Height impacts performance; skewed trees degrade to lists.

2.2 Why This Matters

Trees model hierarchical data and enable efficient searching when balanced. BSTs are central to ordered maps and sets.

2.3 Historical Context / Background

Binary search trees date back to early database indexing and set implementations. Balanced trees (AVL, red-black) were developed to guarantee performance.

2.4 Common Misconceptions

  • Misconception: BST operations are always O(log n). Reality: Worst-case is O(n) if unbalanced.
  • Misconception: Traversals are interchangeable. Reality: Each has specific semantics.

3. Project Specification

3.1 What You Will Build

A BST library with insert, search, delete, min/max, and traversal outputs, plus a terminal tree visualizer.

3.2 Functional Requirements

  1. Node operations: create, destroy, insert, search.
  2. Delete: handle 0, 1, or 2 child cases.
  3. Traversals: inorder, preorder, postorder, level-order.
  4. Visualization: ASCII tree output.

3.3 Non-Functional Requirements

  • Reliability: Correct handling of delete cases.
  • Usability: Clear API and demo.
  • Performance: Maintain invariants and avoid leaks.

3.4 Example Usage / Output

$ ./bst-demo
> insert 5 2 8 1 3
> inorder
1 2 3 5 8
> delete 2
> inorder
1 3 5 8

3.5 Real World Outcome

You will be able to insert, search, and delete nodes while observing the tree shape. Inorder traversal will always return sorted order if the BST is correct.

4. Solution Architecture

4.1 High-Level Design

┌───────────┐     ┌──────────────┐     ┌─────────────┐
│ CLI/Test  │────▶│ BST Library  │────▶│ Visualizer  │
└───────────┘     └──────────────┘     └─────────────┘

4.2 Key Components

Component Responsibility Key Decisions
bst.c BST operations Recursive vs iterative
traversal.c Traversals Stack vs recursion
visualize.c ASCII rendering Inorder depth layout

4.3 Data Structures

typedef struct Node {
    int key;
    struct Node* left;
    struct Node* right;
} Node;

4.4 Algorithm Overview

Key Algorithm: BST Delete

  1. Find node to delete.
  2. If 0 or 1 child, replace node.
  3. If 2 children, replace with inorder successor.

Complexity Analysis:

  • Time: O(h)
  • Space: O(h) recursion stack

5. Implementation Guide

5.1 Development Environment Setup

cc -Wall -Wextra -o bst-demo src/*.c

5.2 Project Structure

bst/
├── src/
│   ├── bst.c
│   ├── bst.h
│   ├── traversal.c
│   ├── visualize.c
│   └── demo.c
├── tests/
└── README.md

5.3 The Core Question You’re Answering

“How does tree shape affect search performance?”

5.4 Concepts You Must Understand First

Stop and research these before coding:

  1. BST invariant
  2. Inorder traversal meaning
  3. Tree height and balance

5.5 Questions to Guide Your Design

  1. Will you expose Node or hide it behind an API?
  2. Will you allow duplicate keys? If yes, where do they go?
  3. How will you visualize depth in ASCII?

5.6 Thinking Exercise

Insert keys [5, 2, 8, 1, 3] and draw the resulting tree. Then insert [1, 2, 3, 4, 5] and observe skew.

5.7 The Interview Questions They’ll Ask

  1. Implement BST delete and explain cases.
  2. Why does inorder traversal yield sorted output?
  3. How do you balance a BST?

5.8 Hints in Layers

Hint 1: Implement search and insert first Delete is easier once insert works.

Hint 2: Use helper for min node Find inorder successor with a simple helper.

Hint 3: Visualize depth with indentation Indent by depth level to show structure.

5.9 Books That Will Help

Topic Book Chapter
BST operations “Algorithms, Fourth Edition” Ch. 3.2
Tree traversals “Introduction to Algorithms” Ch. 12

5.10 Implementation Phases

Phase 1: Foundation (3-4 days)

Goals:

  • Implement Node, insert, search
  • Add inorder traversal

Tasks:

  1. Build Node creation and insertion.
  2. Add traversal outputs.

Checkpoint: Inorder traversal outputs sorted keys.

Phase 2: Delete and Visualize (4-5 days)

Goals:

  • Implement delete cases
  • Add ASCII visualizer

Tasks:

  1. Implement delete with successor.
  2. Render tree with indentation.

Checkpoint: Delete works for 0, 1, 2 child nodes.

Phase 3: Traversal Suite (2-3 days)

Goals:

  • Add preorder, postorder, level-order
  • Add tests

Tasks:

  1. Add recursive and iterative variants.
  2. Add level-order using queue.

Checkpoint: Traversal outputs match expected orders.

5.11 Key Implementation Decisions

Decision Options Recommendation Rationale
Duplicates left, right, count count Avoid skew
Traversal recursion, stack recursion for clarity Simpler first pass
Visualization sideways, top-down sideways Easier in ASCII

6. Testing Strategy

6.1 Test Categories

Category Purpose Examples
Unit Tests Insert/search Known key sets
Integration Tests Delete cases 0, 1, 2 children
Edge Case Tests Skewed tree Sorted input

6.2 Critical Test Cases

  1. Delete root with two children.
  2. Insert duplicates (if supported).
  3. Level-order traversal correctness.

6.3 Test Data

[5, 2, 8, 1, 3]
[1, 2, 3, 4, 5]

7. Common Pitfalls and Debugging

7.1 Frequent Mistakes

Pitfall Symptom Solution
Not updating parent links Lost nodes Return new subtree root
Incorrect successor handling Missing keys Replace with min in right subtree
Memory leaks Valgrind errors Free deleted node

7.2 Debugging Strategies

  • Print inorder traversal after each insert/delete.
  • Use a small tree to step through delete logic.

7.3 Performance Traps

Inserting sorted input creates a skewed tree with O(n) operations. Note this limitation.

8. Extensions and Challenges

8.1 Beginner Extensions

  • Add height and balance checks.
  • Add search for predecessor/successor.

8.2 Intermediate Extensions

  • Implement AVL or red-black tree.
  • Add range query support.

8.3 Advanced Extensions

  • Implement order statistics tree.
  • Add persistent tree snapshotting.

9. Real-World Connections

9.1 Industry Applications

  • Ordered maps and sets
  • Database indexes and range queries
  • glib: Balanced tree structures.
  • Linux kernel rbtree: Red-black tree implementation.

9.3 Interview Relevance

BST problems are common, especially delete cases and traversals.

10. Resources

10.1 Essential Reading

  • “Algorithms, Fourth Edition” by Sedgewick - Ch. 3.2
  • “Introduction to Algorithms” - Ch. 12

10.2 Video Resources

  • Tree traversal visualizations

10.3 Tools and Documentation

  • Graphviz for tree diagrams: https://graphviz.org

11. Self-Assessment Checklist

11.1 Understanding

  • I can explain BST invariants.
  • I can explain delete with two children.
  • I can compare balanced vs skewed tree performance.

11.2 Implementation

  • All operations pass tests.
  • Traversals output expected sequences.

11.3 Growth

  • I can reason about tree balance and height.

12. Submission / Completion Criteria

Minimum Viable Completion:

  • Insert, search, delete
  • Inorder traversal

Full Completion:

  • All traversals
  • ASCII visualization

Excellence (Going Above and Beyond):

  • Balanced tree implementation
  • Range query support

This guide was generated from LEARN_ALGORITHMS_DEEP_DIVE.md. For the complete learning path, see the parent directory.