Binary trees

About This Module

This module introduces binary trees, a fundamental data structure in computer science. You'll learn about the properties of binary trees, different types of binary trees (such as binary search trees and heaps), and how to implement and traverse them in Rust. The module will also cover common operations on binary trees, including insertion, deletion, and searching.

Prework

Prework Reading

Please read the following sections from The Rust Programming Language Book:

Chapter 3.2: Guessing Game - Focus on input handling and basic control flow
Chapter 4.1: Ownership - Understand how Rust manages memory
Chapter 4.2: References and Borrowing - Learn about references, mutable references, and borrowing rules
Chapter 4.3: The Slice Type - Understand slices and how they relate to arrays and vectors

Pre-lecture Reflections

Before class, consider these questions:

What are the key properties of binary trees that differentiate them from other tree structures?
How do binary search trees maintain order, and what are the implications for search, insertion and deletion operations?
What are the advantages and disadvantages of using binary trees compared to other data structures like arrays or linked lists?
How does Rust's ownership and borrowing system impact the implementation of binary trees?
What are some common applications of binary trees in computer science and software development?

Lecture

Learning Objectives

By the end of this module, you will be able to:

Understand the structure and properties of binary trees
Implement binary trees in Rust
Perform common operations on binary trees, including insertion, deletion, and searching
Traverse binary trees using different algorithms (e.g., in-order, pre-order, post-order)
Recognize different types of binary trees (e.g., binary search trees, heaps) and their use cases
Analyze the time and space complexity of binary tree operations

Trees vs Graphs

Trees are a special type of graph with a few key features

Hierarchical structure with a root node
Acyclic
Parent and child nodes with well-defined ancestry (every node besides the root has only one parent)
Only n-1 edges for n nodes
May constrain the number of children (in a binary tree each parent can have at most two children)

A general tree:

Why are trees useful?

✅ Anything with a hierarchical data structure (e.g., File systems, HTML DOM structure)

File systems: Directories and files form a natural tree—folders contain subfolders and files, and this nesting forms a hierarchy.
HTML DOM: The structure of a webpage is a tree where elements nest inside each other; the root is usually the <html> tag.

🗜 Data compression (Huffman coding)

Builds a binary tree where the most frequent characters are near the top and less frequent ones further down.
Encoding: Each character gets a unique binary string based on its path from the root—shorter for frequent characters.

🧠 Compilers use syntax trees (Abstract Syntax Trees - ASTs)

Represents code structure: A program’s nested expressions, blocks, and statements naturally form a tree.
Compiler passes: Syntax trees are walked recursively for semantic checks, optimization, and code generation.
In Rust: The Rust compiler (rustc) builds and transforms ASTs as part of its pipeline

🔡 Prefix trees (Tries) (discussed below)

Spell checking and autocomplete: Fast prefix search to suggest or validate words.
Internet routing: IP addresses share prefixes, and tries are used for longest prefix match routing.
Memory vs speed tradeoff: Tries use more memory but offer O(k) search time, where k is the key length.

💾 Databases use trees for indexing (e.g., B-trees, B+ trees)

Efficient range queries and lookups: Balanced trees ensure O(log n) insert/search/delete.
Disk-friendly: B-trees minimize disk reads by keeping nodes wide and shallow.
Used in practice: PostgreSQL, SQLite, and others use variants of B-trees for indexing.

🔐 Merkle trees

Used in blockchains: Efficient verification of large data sets by checking only a small number of hashes.
Tamper detection: Changing one leaf changes hashes all the way up—perfect for integrity checking.
Applications: Bitcoin, Git, BitTorrent, and more rely on Merkle trees.

🌐 Spanning trees in networks

Minimal spanning tree (MST): Ensures all nodes in a network are connected with minimal total edge weight.
Used in routing: Algorithms like Kruskal’s or Prim’s help avoid loops in protocols like Ethernet (Spanning Tree Protocol).

🌳 Decision trees

Machine learning: Trees split data based on feature thresholds to make predictions.
Easy to interpret: Each path in the tree represents a rule for classification.

🔃 Sorting algorithms

Binary heaps: Used in heap sort—trees where the parent is smaller/larger than children.
BST-based sorts: In-order traversal of a Binary Search Tree gives sorted order.
AVL/Red-Black Trees: Self-balancing trees used to maintain order during dynamic inserts/deletes.

🔍 Search algorithms

Binary Search Trees (BSTs): Allow for fast search, insert, and delete in O(log n) time if balanced.
Trie-based search: Efficient for prefix and word lookup.
Tree traversal: DFS and BFS strategies apply directly—recursion meets queue/stack use in Rust.

Important Terms

Root - the topmost node of the tree, only node without a parent
Ancestor vs Descendant - If two nodes are connected, the node that is closer to the root is the ancestor of the other node, similarly the further node its descendant
Parent vs Child - A nodes immediate descendant is its child, and a nodes immediate ancestor is its parent
Leaf - a node with no child nodes
Subtree - A subset of the tree, with a parent of the original tree becoming the root of the subtree
Depth - the greatest number of descendants between the root and a leaf node
Level - the number of edges between a node and the root. Root node has level 0
Sibling - nodes that share the same parent

Why are binary trees useful?

Simple to analyze
Many algorithms boil down to a series of "True/False" decisions that map well to binary trees
Ordering in particular fits well (either you are "<" or you aren't)
Easy to use with recursive algorithms

What types of binary trees are there?

Complete (every level except the last one are full)
Perfect (all leaves are at the same level, all interior nodes have 2 children)
Balanced (left and right subtrees differ by at most 1 level)
Special
- Binary Heaps
- Binary Search Trees

Any other interesting trees?

Prefix trees or tries

Using Vectors to implement a Binary Tree

TreeNode struct and new() method

#[derive(Debug)]
struct TreeNode {
    value: usize,
    left: Option<usize>,
    right: Option<usize>,
}

impl TreeNode {
    // Constructor method
    // This method creates a new TreeNode with the given value
    // and initializes left and right child pointers to None
    fn new(value: usize) -> Self {
        TreeNode {
            value,
            left: None,
            right: None,
        }
    }
}

BinaryTree struct and methods

#[derive(Debug)]
struct BinaryTree {
    // A vector of TreeNode structs
    // The index of the vector is the node index
    nodes: Vec<TreeNode>,
    root: Option<usize>,
}

impl BinaryTree {
    // Constructor method
    // This method creates a new BinaryTree with an empty vector of nodes
    // and a root pointer set to None
    fn new() -> Self {
        BinaryTree { nodes: Vec::new(), root: None }
    }

    fn insert(&mut self, value: usize) {
        let new_node_index = self.nodes.len();
        self.nodes.push(TreeNode::new(value));

        match self.root {
            Some(root_index) => self.insert_at(root_index, new_node_index),
            None => self.root = Some(new_node_index),
        }
    }

    // Inserts a new node into a binary tree by updating the left or right child
    // index of the current node, or if full, a left child node.
    // * Start at the specified current node index:
    //   * if both children are empty, insert the left child
    //   * if left child is occupied, insert the right child
    //   * if both children are occupied, recursively attempt to insert the new
    //     node in the left subtree
    fn insert_at(&mut self, current_index: usize, new_node_index: usize) {
        let current_node = &mut self.nodes[current_index];
        if current_node.left.is_none() {
            current_node.left = Some(new_node_index);
        } else if current_node.right.is_none() {
            current_node.right = Some(new_node_index);
        } else {
            // Insert in left subtree for simplicity, could be more complex to keep balanced
            let left = current_node.left.unwrap();
            self.insert_at(left, new_node_index);
        }
    }
    
}

Remember that left and right are indices, but value is the value we associated with the node.

Predict the BinaryTree structure as we repeatedly insert.

let mut tree = BinaryTree::new();
tree.insert(1);
tree.insert(2);
tree.insert(3);
tree.insert(6);
tree.insert(7);
tree.insert(11);
tree.insert(23);
tree.insert(34);

println!("{:#?}", tree);

BinaryTree {
    nodes: [
        TreeNode {
            value: 1,
            left: Some(
                1,
            ),
            right: Some(
                2,
            ),
        },
        TreeNode {
            value: 2,
            left: Some(
                3,
            ),
            right: Some(
                4,
            ),
        },
        TreeNode {
            value: 3,
            left: None,
            right: None,
        },
        TreeNode {
            value: 6,
            left: Some(
                5,
            ),
            right: Some(
                6,
            ),
        },
        TreeNode {
            value: 7,
            left: None,
            right: None,
        },
        TreeNode {
            value: 11,
            left: Some(
                7,
            ),
            right: None,
        },
        TreeNode {
            value: 23,
            left: None,
            right: None,
        },
        TreeNode {
            value: 34,
            left: None,
            right: None,
        },
    ],
    root: Some(
        0,
    ),
}

Reminder: The numbers in the circles are the values, not the indices of the node.

This isn't super readable, is there a better way to output this tree?

Tree Traversal

There are several ways to traverse trees using algorithms we have seen before:

Using BFS
- Level-order Traversal
Using DFS
- Pre-order Traversal
- In-order Traversal
- Post Order Traversal

We are going to use level-order traversal to visit each level of the tree in order

Level-Order Traversal (BFS)

Just like before.

Create an empty queue
Add the root of tree to queue
While the queue is not empty
- Remove node from queue and visit it
- Add the left child of node to the queue if it exists
- Add the right child of node to the queue if it exists

use std::collections::VecDeque;
fn level_order_traversal(tree: &BinaryTree) {
  if let Some(root_index) = tree.root {
    let mut queue = VecDeque::new();
    queue.push_back(root_index);
    while let Some(node_index) = queue.pop_front() {
      let node = &tree.nodes[node_index];
      println!("{}", node.value);
      if let Some(left_index) = node.left {
        queue.push_back(left_index);
      }
      if let Some(right_index) = node.right {
        queue.push_back(right_index);
      }
    }
  }
}

let mut tree2 = BinaryTree::new();
tree2.insert(1);
tree2.insert(2);
tree2.insert(3);
tree2.insert(6);
tree2.insert(7);
tree2.insert(11);
tree2.insert(23);
tree2.insert(34);
level_order_traversal(&tree2);

// Slightly more complex version that prints each level on a different line
use std::collections::VecDeque;
fn level_order_traversal2(tree: &BinaryTree) {
  if let Some(root_index) = tree.root {
    let mut queue = VecDeque::new();
    queue.push_back(root_index);
    while !queue.is_empty() {
      let level_size = queue.len();
        for _ in 0..level_size {
          if let Some(node_index) = queue.pop_front() {
            let node = &tree.nodes[node_index];
            print!("{} ", node.value);

            if let Some(left_index) = node.left {
              queue.push_back(left_index);
            }
            if let Some(right_index) = node.right {
              queue.push_back(right_index);
            }
        }
      }
      println!(); // New line after each level
    }
  }
}

let mut tree2 = BinaryTree::new();
tree2.insert(1);
tree2.insert(2);
tree2.insert(3);
tree2.insert(6);
tree2.insert(7);
tree2.insert(11);
tree2.insert(23);
tree2.insert(34);
level_order_traversal2(&tree2);

Depth Traversals

Pre-Order Traversal

Often used when making a copy of a tree, uses DFS

Algorithm:

Visit the current node (e.g. print the current node value)
Recursively traverse the current node's left subtree
Recursively traverse the current node's right subtree

The pre-order traversal is a topologically sorted one, because a parent node is processed before any of its child nodes is done.

Reminder: The numbers in the circles are the values, not the indices of the node.

fn pre_order_traversal(tree: &BinaryTree, node_index: Option<usize>) {
  if let Some(index) = node_index {        // If the node index is not None
    let node = &tree.nodes[index];         // Get the node at the index
    println!("{}", node.value);            // Visit (print) the current node value
    pre_order_traversal(tree, node.left);  // Traverse the left subtree
    pre_order_traversal(tree, node.right); // Traverse the right subtree
  }
}

pre_order_traversal(&tree2, tree2.root)

In-Order Traversal

In-Order traversal:

Recursively traverse the current node's left subtree.
Visit the current node (e.g. print the node's current value).
Recursively traverse the current node's right subtree.

In a binary search tree ordered such that in each node the value is greater than all values in its left subtree and less than all values in its right subtree, in-order traversal retrieves the keys in ascending sorted order.

Reminder: The numbers in the circles are the values, not the indices of the node.

How do we update pre_order_traversal() to get in_order_traversal()?

fn in_order_traversal(tree: &BinaryTree, node_index: Option<usize>) {
    if let Some(index) = node_index {       // If the node index is not None
      let node = &tree.nodes[index];        // Get the node at the index
      in_order_traversal(tree, node.left);  // Traverse the left subtree
      println!("{}", node.value);           // Visit (print) the current node value
      in_order_traversal(tree, node.right); // Traverse the right subtree
    }
  }
  
  in_order_traversal(&tree2, tree2.root)

Post-Order traversal

Good for deleting the tree or parts of it, must delete children before parents:

Recursively traverse the current node's left subtree.
Recursively traverse the current node's right subtree.
Visit the current node.

Reminder: The numbers in the circles are the values, not the indices of the node.

How do we update in_order_traversal() to post_order_traversal()?

fn post_order_traversal(tree: &BinaryTree, node_index: Option<usize>) {
    if let Some(index) = node_index {       // If the node index is not None
      let node = &tree.nodes[index];        // Get the node at the index
      post_order_traversal(tree, node.left);  // Traverse the left subtree
      post_order_traversal(tree, node.right); // Traverse the right subtree
      println!("{}", node.value);           // Visit (print) the current node value
    }
  }
  
  post_order_traversal(&tree2, tree2.root)

DS210 Course Notes

Binary trees

About This Module

Prework

Prework Reading

Pre-lecture Reflections

Lecture

Learning Objectives

Trees vs Graphs

Why are trees useful?

✅ Anything with a hierarchical data structure (e.g., File systems, HTML DOM structure)

🗜 Data compression (Huffman coding)

🧠 Compilers use syntax trees (Abstract Syntax Trees - ASTs)

🔡 Prefix trees (Tries) (discussed below)

💾 Databases use trees for indexing (e.g., B-trees, B+ trees)

🔐 Merkle trees

🌐 Spanning trees in networks

🌳 Decision trees

🔃 Sorting algorithms

🔍 Search algorithms

Important Terms

Why are binary trees useful?

What types of binary trees are there?

Any other interesting trees?

Using Vectors to implement a Binary Tree

TreeNode struct and new() method

BinaryTree struct and methods

Tree Traversal

Level-Order Traversal (BFS)

Depth Traversals

Pre-Order Traversal

In-Order Traversal

Post-Order traversal

Technical Coding Challenge

Coding Challenge

Coding Challenge Review