Binary Tree

A binary tree is a tree data structure in which each node has at most two children, commonly referred to as the left and right child. Binary trees form the foundation for many advanced data structures, including binary search trees, heaps, and balanced trees.

Unlike binary search trees, a plain binary tree does not impose any ordering rules on its elements.

Structure of a Binary Tree

Each node in a binary tree contains:

A value
An optional left child
An optional right child

In this example:

A is the root
B and C are children of A
D and E are children of B

Key Properties

Each node has 0, 1, or 2 children
There is exactly one root
There are no cycles
Left and right children are distinct positions

Common Binary Tree Types

Full Binary Tree

Every node has either 0 or 2 children.

Complete Binary Tree

All levels are completely filled except possibly the last, which is filled from left to right.

Perfect Binary Tree

All internal nodes have two children and all leaves are at the same level.

These distinctions matter later when working with heaps and balanced trees.

Representing a Binary Tree in Rust

Unlike languages with built-in reference types, Rust requires explicit handling of ownership. A common and safe approach is to use Box and Option.

Rust Implementation

Below is a minimal binary tree node definition that supports left and right children.

#[derive(Debug)]
pub struct Node<T> {
    pub value: T,
    pub left: Option<Box<Node<T>>>,
    pub right: Option<Box<Node<T>>>,
}

impl<T> Node<T> {
    pub fn new(value: T) -> Self {
        Node {
            value,
            left: None,
            right: None,
        }
    }
}

This structure allows:

Safe ownership of child nodes
Recursive tree construction
Clear parent-child relationships

Building a Simple Binary Tree

fn main() {
    let mut root = Node::new(1);

    root.left = Some(Box::new(Node::new(2)));
    root.right = Some(Box::new(Node::new(3)));

    if let Some(ref mut left) = root.left {
        left.left = Some(Box::new(Node::new(4)));
        left.right = Some(Box::new(Node::new(5)));
    }

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

This creates the following tree:

Why Binary Trees Matter

Binary trees are the building blocks for many core algorithms and data structures:

Binary Search Trees - fast lookup
Heaps - priority queues
Expression Trees - parsing and evaluation
Decision Trees - machine learning

Understanding their structure is essential before learning traversal and ordering rules.

Playground Links

Rust - Binary Tree