Tree | Dheerendra Varma

What is a Tree?

A tree is a connected, acyclic graph with a designated root node. Every non-root node has exactly one parent, and there are no cycles. The recursive definition is powerful: a tree is either empty, or a root node plus zero or more subtrees (each itself a tree).

Key vocabulary: the root is the topmost node with no parent. A leaf is a node with no children. An internal node has at least one child. The depth of a node is its distance from the root (root has depth 0). The height of a node is the length of the longest path to any descendant leaf. The height of the tree equals the height of the root. A subtree rooted at node v is v together with all its descendants.

Applications

File systems are trees: directories contain files and subdirectories. The HTML DOM is a tree of elements. Compilers build abstract syntax trees to represent program structure before generating code. Organisation charts are trees of reporting relationships. Decision trees in machine learning split data recursively. XML and JSON documents are trees. Package dependency graphs that contain no cycles are also trees.

Representations

The most flexible representation for a general n-ary tree in Rust is an adjacency list — a Vec<Vec<usize>> where index i holds the list of children of node i. Node values are stored separately.

use std::collections::VecDeque;
 
struct NaryTree {
    children: Vec<Vec<usize>>,
    vals: Vec<i32>,
}
 
impl NaryTree {
    fn new(n: usize, vals: Vec<i32>) -> Self {
        NaryTree { children: vec![vec![]; n], vals }
    }
 
    fn add_edge(&mut self, parent: usize, child: usize) {
        self.children[parent].push(child);
    }
}

A parent-array representation stores parent[i] = the parent index of node i (root's parent is itself or a sentinel). It is compact and fast for root-to-node path queries.

fn build_parent_array(edges: &[(usize, usize)], n: usize) -> Vec<usize> {
    let mut parent = (0..n).collect::<Vec<_>>();
    for &(p, c) in edges {
        parent[c] = p;
    }
    parent
}

A struct-based n-ary tree uses Vec<Box<TreeNode>> for children. This is natural but makes it harder to pass references mutably across function calls due to Rust's ownership rules. The adjacency list avoids this friction for algorithmic work.

Operations and Time Complexity

Operation	Time	Notes
Add child	O(1)	Append to children list
Get children	O(degree)	Iterate children
Height	O(n)	Must visit every node
BFS traversal	O(n)	Visit each node once
DFS traversal	O(n)	Visit each node once
Path to root	O(depth)	With parent array
LCA (naive)	O(depth)	Walk both nodes to root

Implementation in Rust

use std::collections::VecDeque;
 
struct Tree {
    children: Vec<Vec<usize>>,
    vals: Vec<i32>,
    n: usize,
}
 
impl Tree {
    fn new(vals: Vec<i32>) -> Self {
        let n = vals.len();
        Tree { children: vec![vec![]; n], vals, n }
    }
 
    fn add_edge(&mut self, parent: usize, child: usize) {
        self.children[parent].push(child);
    }
 
    fn height(&self, node: usize) -> usize {
        if self.children[node].is_empty() { return 0; }
        self.children[node]
            .iter()
            .map(|&c| 1 + self.height(c))
            .max()
            .unwrap_or(0)
    }
 
    fn bfs(&self, root: usize) -> Vec<i32> {
        let mut result = Vec::new();
        let mut queue = VecDeque::new();
        queue.push_back(root);
        while let Some(node) = queue.pop_front() {
            result.push(self.vals[node]);
            for &child in &self.children[node] {
                queue.push_back(child);
            }
        }
        result
    }
 
    fn dfs_preorder(&self, node: usize, result: &mut Vec<i32>) {
        result.push(self.vals[node]);
        for &child in &self.children[node] {
            self.dfs_preorder(child, result);
        }
    }
 
    fn dfs_postorder(&self, node: usize, result: &mut Vec<i32>) {
        for &child in &self.children[node] {
            self.dfs_postorder(child, result);
        }
        result.push(self.vals[node]);
    }
}

Fundamental Algorithms and Problems

Subtree Size — Post-Order DFS

Compute the number of nodes in each subtree using post-order DFS. A node's subtree size equals 1 (itself) plus the sum of its children's subtree sizes. Post-order ensures children are processed before their parent.

fn subtree_sizes(adj: &Vec<Vec<usize>>, node: usize, parent: usize, sizes: &mut Vec<usize>) {
    sizes[node] = 1;
    for &child in &adj[node] {
        if child == parent { continue; } // undirected tree: skip parent
        subtree_sizes(adj, child, node, sizes);
        sizes[node] += sizes[child];
    }
}
 
fn main() {
    let n = 6;
    // Tree: 0-1, 0-2, 1-3, 1-4, 2-5
    let mut adj = vec![vec![]; n];
    for (u, v) in [(0,1),(0,2),(1,3),(1,4),(2,5)] {
        adj[u].push(v); adj[v].push(u);
    }
    let mut sizes = vec![0; n];
    subtree_sizes(&adj, 0, usize::MAX, &mut sizes);
    println!("{:?}", sizes); // [6, 3, 2, 1, 1, 1]
}

Tree Height via DFS

The height of a tree is the length of the longest root-to-leaf path. Recursively, height(node) = 0 if leaf, else 1 + max(height(child) for each child). This is a post-order computation.

fn tree_height(adj: &Vec<Vec<usize>>, node: usize, parent: usize) -> usize {
    adj[node]
        .iter()
        .filter(|&&c| c != parent)
        .map(|&c| 1 + tree_height(adj, c, node))
        .max()
        .unwrap_or(0)
}
 
fn main() {
    let n = 5;
    let mut adj = vec![vec![]; n];
    for (u, v) in [(0,1),(0,2),(1,3),(1,4)] {
        adj[u].push(v); adj[v].push(u);
    }
    println!("height: {}", tree_height(&adj, 0, usize::MAX)); // 2
}

Diameter of a Tree

The diameter is the longest path between any two nodes. A single DFS computes it: for each node, find the two longest paths to leaves among all child subtrees. The diameter candidate through this node is the sum of the two longest. Track the global maximum.

fn diameter_dfs(adj: &Vec<Vec<usize>>, node: usize, parent: usize, diameter: &mut usize) -> usize {
    let mut top1 = 0usize; // longest child path
    let mut top2 = 0usize; // second longest
 
    for &child in &adj[node] {
        if child == parent { continue; }
        let h = 1 + diameter_dfs(adj, child, node, diameter);
        if h > top1 { top2 = top1; top1 = h; }
        else if h > top2 { top2 = h; }
    }
    *diameter = (*diameter).max(top1 + top2);
    top1
}
 
fn main() {
    let n = 6;
    let mut adj = vec![vec![]; n];
    for (u, v) in [(0,1),(0,2),(1,3),(3,4),(3,5)] {
        adj[u].push(v); adj[v].push(u);
    }
    let mut diam = 0;
    diameter_dfs(&adj, 0, usize::MAX, &mut diam);
    println!("diameter: {}", diam); // 4  (path 2-0-1-3-4 or 2-0-1-3-5)
}

Lowest Common Ancestor — Parent Array

Given two nodes u and v, find their lowest common ancestor using depth and parent arrays. Bring both nodes to the same depth by walking the deeper one up, then walk both up together until they meet. This takes O(depth) time and O(n) preprocessing.

fn build_depth_parent(adj: &Vec<Vec<usize>>, root: usize, n: usize) -> (Vec<usize>, Vec<usize>) {
    let mut depth = vec![0usize; n];
    let mut parent = vec![root; n];
    let mut queue = VecDeque::new();
    let mut visited = vec![false; n];
    queue.push_back(root);
    visited[root] = true;
 
    while let Some(node) = queue.pop_front() {
        for &child in &adj[node] {
            if !visited[child] {
                visited[child] = true;
                parent[child] = node;
                depth[child] = depth[node] + 1;
                queue.push_back(child);
            }
        }
    }
    (depth, parent)
}
 
fn lca(depth: &[usize], parent: &[usize], mut u: usize, mut v: usize) -> usize {
    while depth[u] > depth[v] { u = parent[u]; }
    while depth[v] > depth[u] { v = parent[v]; }
    while u != v { u = parent[u]; v = parent[v]; }
    u
}
 
fn main() {
    let n = 7;
    let mut adj = vec![vec![]; n];
    for (u, v) in [(0,1),(0,2),(1,3),(1,4),(2,5),(2,6)] {
        adj[u].push(v); adj[v].push(u);
    }
    let (depth, parent) = build_depth_parent(&adj, 0, n);
    println!("LCA(3,4) = {}", lca(&depth, &parent, 3, 4)); // 1
    println!("LCA(3,5) = {}", lca(&depth, &parent, 3, 5)); // 0
    println!("LCA(5,6) = {}", lca(&depth, &parent, 5, 6)); // 2
}

Count Nodes at Each Level — BFS

BFS naturally processes nodes level by level. Snapshotting the queue length at the start of each iteration gives the count of nodes at the current level.

use std::collections::VecDeque;
 
fn level_counts(adj: &Vec<Vec<usize>>, root: usize, n: usize) -> Vec<usize> {
    let mut visited = vec![false; n];
    let mut queue = VecDeque::new();
    let mut counts = Vec::new();
 
    visited[root] = true;
    queue.push_back(root);
 
    while !queue.is_empty() {
        let level_size = queue.len();
        counts.push(level_size);
        for _ in 0..level_size {
            let node = queue.pop_front().unwrap();
            for &child in &adj[node] {
                if !visited[child] {
                    visited[child] = true;
                    queue.push_back(child);
                }
            }
        }
    }
    counts
}
 
fn main() {
    let n = 7;
    let mut adj = vec![vec![]; n];
    for (u, v) in [(0,1),(0,2),(1,3),(1,4),(2,5),(2,6)] {
        adj[u].push(v); adj[v].push(u);
    }
    println!("{:?}", level_counts(&adj, 0, n)); // [1, 2, 4]
}