Binary Trees - Complete Implementation

A comprehensive, educational implementation of Binary Tree and Binary Search Tree data structures in Python. Designed for teaching computer science students with clear code, extensive documentation, and practical demonstrations.

Overview

This repository provides production-quality implementations of:

• TreeNode: Foundation class representing individual tree nodes
• BinaryTree: General binary tree with traversals and tree properties
• BinarySearchTree: BST with efficient insert, delete, and search operations
• ExpressionTree: Evaluate and parse mathematical expressions with multiple notations
• DecisionTree: Model binary decision-making processes for automated triage and classification

All code includes type hints, comprehensive docstrings, complexity analysis, and is backed by comprehensive tests.

Quick Start

Installation

# Clone the repository
git clone <your-repo-url>
cd binary_trees

# Install with uv (recommended)
uv sync

# Or use pip
pip install -e .

Run the Demos

# Binary Tree and Binary Search Tree
uv run python demos/basic_demo.py

# Expression Tree
uv run python demos/expression_tree_demo.py

# Decision Tree
uv run python demos/decision_tree_demo.py

Run Tests

uv run pytest src/ -v

Features

TreeNode Class

Simple, clean node implementation:

from src.treenode import TreeNode

# Create nodes
root = TreeNode(10)
root.left = TreeNode(5)
root.right = TreeNode(15)

BinaryTree Class

General binary tree with comprehensive methods:

Core Operations:

• is_empty() - Check if tree is empty
• size() - Count total nodes
• height() - Calculate tree height

Traversal Methods:

• inorder() - Left → Root → Right
• preorder() - Root → Left → Right
• postorder() - Left → Right → Root
• levelorder() - Breadth-first traversal

Tree Properties:

• is_balanced() - Check height-balanced property
• is_complete() - Check if all levels full except possibly last
• is_full() - Check if every node has 0 or 2 children
• is_perfect() - Check if all leaves at same level

Search Operations:

• contains(val) - Check if value exists
• find(val) - Find node with value
• leaves() - Get all leaf nodes

Utilities:

• __str__() - Beautiful ASCII tree visualization
• to_list() - Serialize to list
• from_list(values) - Build tree from list

BinarySearchTree Class

Extends BinaryTree with BST-specific operations:

Core BST Operations:

• insert(val) - Add value maintaining BST property
• delete(val) - Remove value (handles all 3 cases)
• search(val) - Efficient O(log n) lookup
• search_with_path(val) - Search with path tracking (educational)

Min/Max Operations:

• find_min() - Get minimum value
• find_max() - Get maximum value

Validation:

• is_valid_bst() - Verify BST property

Construction:

• from_list(values) - Build BST from values
• from_sorted_list(values) - Build balanced BST from sorted values

Example Usage

Binary Tree Example

from src.binary_tree import BinaryTree
from src.treenode import TreeNode

# Create a tree
root = TreeNode(1)
root.left = TreeNode(2)
root.right = TreeNode(3)
root.left.left = TreeNode(4)
root.left.right = TreeNode(5)

tree = BinaryTree(root)

# Visualize
print(tree)
# Output:
# 1
#     ├── 3
#     └── 2
#         ├── 5
#         └── 4

# Get properties
print(f"Height: {tree.height()}")        # 2
print(f"Size: {tree.size()}")            # 5
print(f"Balanced: {tree.is_balanced()}")  # True

# Traverse
print(f"In-order: {tree.inorder()}")      # [4, 2, 5, 1, 3]
print(f"Level-order: {tree.levelorder()}")  # [[1], [2, 3], [4, 5]]

Binary Search Tree Example

from src.binary_search_tree import BinarySearchTree

# Create BST and insert values
bst = BinarySearchTree()
values = [50, 30, 70, 20, 40, 60, 80]
for val in values:
    bst.insert(val)

# Visualize
print(bst)
# Output:
# 50
#     ├── 70
#     │   ├── 80
#     │   └── 60
#     └── 30
#         ├── 40
#         └── 20

# Search with path tracking
found, path = bst.search_with_path(40)
print(f"Found: {found}, Path: {' → '.join(map(str, path))}")
# Output: Found: True, Path: 50 → 30 → 40

# In-order gives sorted sequence
print(bst.inorder())  # [20, 30, 40, 50, 60, 70, 80]

# Delete operations (handles all 3 cases)
bst.delete(20)  # Case 1: Leaf node
bst.delete(30)  # Case 2: One child
bst.delete(50)  # Case 3: Two children

print(bst.inorder())  # [40, 60, 70, 80]
print(f"Valid BST: {bst.is_valid_bst()}")  # True

Expression Tree Example

from src.expression_tree import ExpressionTree

# Build from postfix notation
tree = ExpressionTree.from_postfix("3 5 + 2 *")

# Visualize
print(tree)
# Output:
# *
#     ├── 2
#     └── +
#         ├── 5
#         └── 3

# Convert between notations
print(tree.to_infix())    # ((3 + 5) * 2)
print(tree.to_prefix())   # * + 3 5 2
print(tree.to_postfix())  # 3 5 + 2 *

# Evaluate
print(tree.evaluate())    # 16.0

# Build from prefix notation
tree2 = ExpressionTree.from_prefix("- * + 4 2 3 1")
print(tree2.to_infix())   # (((4 + 2) * 3) - 1)
print(tree2.evaluate())   # 17.0

Decision Tree Example

from src.decision_tree import DecisionNode, DecisionTree

# Build a support triage tree
general = DecisionNode("General Support")
billing = DecisionNode("Billing Team")
tier2 = DecisionNode("Tier 2 Support")
emergency = DecisionNode("Emergency Response")

billing_q = DecisionNode("Is it billing?", general, billing)
system_q = DecisionNode("System down?", tier2, emergency)
root = DecisionNode("Is it urgent?", billing_q, system_q)

tree = DecisionTree(root)

# Visualize
print(tree)
# Output:
# Is it urgent??
#     ├── (Yes)
#     │   └── System down??
#     │       ├── (Yes)
#     │       │   └── [Emergency Response]
#     │       └── (No)
#     │           └── [Tier 2 Support]
#     └── (No)
#         └── Is it billing??
#             ├── (Yes)
#             │   └── [Billing Team]
#             └── (No)
#                 └── [General Support]

# Make decisions programmatically
print(tree.decide([False, False]))  # "General Support"
print(tree.decide([True, True]))    # "Emergency Response"

# Get all possible outcomes
outcomes = tree.get_all_outcomes()
print(outcomes)  # ['Tier 2 Support', 'Emergency Response', 'General Support', 'Billing Team']

# Find path to specific outcome
path = tree.get_path_to_outcome("Billing Team")
# Returns: [("Is it urgent?", False), ("Is it billing?", True)]

# Analyze decision complexity
depth = tree.depth_to_outcome("Emergency Response")
print(depth)  # 2 (requires 2 questions)

Building Balanced BST

from src.binary_search_tree import BinarySearchTree

# Regular insertion creates unbalanced tree
sorted_vals = [1, 2, 3, 4, 5, 6, 7]
bst_unbalanced = BinarySearchTree.from_list(sorted_vals)
print(f"Height: {bst_unbalanced.height()}")  # 6 (essentially a linked list)

# Use from_sorted_list for balanced tree
bst_balanced = BinarySearchTree.from_sorted_list(sorted_vals)
print(f"Height: {bst_balanced.height()}")    # 2 (optimal)
print(f"Balanced: {bst_balanced.is_balanced()}")  # True

Time Complexity

Binary Tree Operations

Operation	Time Complexity	Space Complexity
Traversals	O(n)	O(h) recursion
Height	O(n)	O(h) recursion
Size	O(n)	O(h) recursion
Contains	O(n)	O(w) queue
Is Balanced	O(n)	O(h) recursion

Binary Search Tree Operations

Operation	Average	Worst Case	Space
Search	O(log n)	O(n)	O(1)
Insert	O(log n)	O(n)	O(log n)
Delete	O(log n)	O(n)	O(log n)
Find Min/Max	O(log n)	O(n)	O(1)

Note: Worst case O(n) occurs with unbalanced trees (linked lists). Use from_sorted_list() to build balanced trees.

Expression Tree Operations

Operation	Time Complexity	Space Complexity
Evaluate	O(n)	O(h) recursion
To Infix/Prefix/Postfix	O(n)	O(h) recursion
From Postfix	O(n)	O(n) stack
From Prefix	O(n)	O(n) stack

Decision Tree Operations

Operation	Time Complexity	Space Complexity
Decide	O(h)	O(1)
Get All Outcomes	O(n)	O(n)
Get Path to Outcome	O(n)	O(h) recursion
Depth to Outcome	O(n)	O(h) recursion

Project Structure

binary_trees/
├── src/
│   ├── treenode.py                 # TreeNode class
│   ├── binary_tree.py              # BinaryTree class
│   ├── binary_search_tree.py       # BinarySearchTree class
│   ├── expression_tree.py          # ExpressionTree class
│   ├── decision_tree.py            # DecisionTree class
│   ├── test_treenode.py            # TreeNode tests
│   ├── test_binary_tree.py         # BinaryTree tests
│   ├── test_binary_search_tree.py  # BST tests
│   ├── test_expression_tree.py     # ExpressionTree tests
│   └── test_decision_tree.py       # DecisionTree tests
├── demos/
│   ├── basic_demo.py               # BinaryTree & BST demo
│   ├── expression_tree_demo.py     # ExpressionTree demo
│   └── decision_tree_demo.py       # DecisionTree demo
├── README.md
└── pyproject.toml

Educational Features

This implementation is specifically designed for teaching:

1. Clear Code Structure: Each class has a single responsibility
2. Comprehensive Documentation: Every method includes docstrings with complexity analysis
3. Type Hints: Full type annotations for better IDE support and learning
4. Extensive Tests: Comprehensive test coverage for all tree types
5. Educational Methods: search_with_path() shows search progression
6. Visualization: ASCII tree printing for easy understanding
7. Deletion Cases: BST delete handles all 3 standard cases with clear comments
8. Real-World Applications: Expression evaluation and decision automation examples

Key Insights for Students

BST Properties

• BST Invariant: Left < Root < Right for every node
• In-order traversal of BST produces sorted sequence
• Search efficiency: O(log n) average by eliminating half the tree each step
• Balance matters: Unbalanced trees degrade to O(n) operations

Deletion Cases

The BST delete operation handles three cases:

1. Leaf node (no children): Simply remove
2. One child: Replace node with its child
3. Two children: Replace with inorder successor (smallest in right subtree)

Traversal Use Cases

• In-order: Get sorted values from BST
• Pre-order: Copy tree structure, serialize
• Post-order: Delete nodes, calculate tree properties (used in expression evaluation)
• Level-order: Print tree level by level, find shortest path

Expression Trees

• Leaf nodes contain operands (numbers)
• Internal nodes contain operators (+, -, *, /, //, %, **)
• Postorder traversal naturally evaluates the expression (process children before parent)
• Notation conversions:
  • Infix: Human-readable with parentheses ((3 + 5) * 2)
  • Prefix: Operator first (Polish notation) * + 3 5 2
  • Postfix: Operator last (RPN) 3 5 + 2 *

Decision Trees

• Internal nodes contain questions (binary decisions)
• Left branch represents "No" or False
• Right branch represents "Yes" or True
• Leaf nodes contain outcomes or actions
• Use cases: Automated triage, troubleshooting guides, classification systems
• Path depth indicates decision complexity (number of questions needed)

Testing

Run all 82 tests:

# Run all tests
uv run pytest src/ -v

# Run specific test file
uv run pytest src/test_binary_search_tree.py -v

# Run with coverage
uv run pytest src/ --cov=src --cov-report=html

Contributing

This is an educational repository. Contributions that improve clarity, add educational value, or fix bugs are welcome.

License

MIT License - Free to use for educational purposes.

Author

Created for computer science education and technical interview preparation.

---

Perfect for:

• Data structures courses
• Technical interview preparation
• Algorithm study groups
• CS student reference material
• Teaching recursion and tree concepts
• Understanding expression parsing and evaluation
• Learning decision tree algorithms and automation