Binary Tree
Each node has at most two children — left and right. This constraint creates four distinct traversal orderings and a recursive structure that appears in compilers, compression, and nearly every advanced tree problem.
What is a Binary Tree?
A binary tree is a tree where every node has at most two children, conventionally called the left child and the right child. This constraint is small but consequential: it gives traversals a canonical ordering (in-order, pre-order, post-order), enables the array representation for complete trees, and forms the foundation of BSTs, heaps, and segment trees.
Terminology: a full binary tree has every node with 0 or 2 children. A complete binary tree fills all levels left to right, with the last level possibly incomplete. A perfect binary tree has all leaf nodes at the same depth, meaning all n levels are fully filled and the tree has 2ⁿ - 1 nodes. A degenerate tree has every internal node with only one child — it behaves like a linked list.
Applications
Expression trees represent arithmetic expressions: (3 + 4) * 2 becomes a tree with * at the root, + as the left child, and 2 as the right. Huffman coding builds a binary tree from character frequencies to produce optimal variable-length codes for compression. Segment trees and Fenwick trees are binary trees used for range queries. Heaps are complete binary trees stored as arrays. BSTs are binary trees with an ordering property.
Representations
The standard linked representation uses Option<Box<TreeNode>> — Option because a child may be absent, Box to allocate the node on the heap and transfer ownership.
#[derive(Debug)]
struct TreeNode {
val: i32,
left: Option<Box<TreeNode>>,
right: Option<Box<TreeNode>>,
}
impl TreeNode {
fn new(val: i32) -> Box<Self> {
Box::new(TreeNode { val, left: None, right: None })
}
}
// Build: 1
// / \
// 2 3
// / \
// 4 5
fn sample_tree() -> Option<Box<TreeNode>> {
let mut root = TreeNode::new(1);
let mut two = TreeNode::new(2);
two.left = Some(TreeNode::new(4));
two.right = Some(TreeNode::new(5));
root.left = Some(two);
root.right = Some(TreeNode::new(3));
Some(root)
}For complete binary trees, the array representation stores nodes in BFS order: the node at index i has its left child at 2i+1 and right child at 2i+2. This is how heaps are stored and avoids pointer overhead entirely.
fn left_child(i: usize) -> usize { 2 * i + 1 }
fn right_child(i: usize) -> usize { 2 * i + 2 }
fn parent(i: usize) -> usize { (i - 1) / 2 }
fn array_tree_demo() {
let tree = vec![1, 2, 3, 4, 5, 6, 7];
// tree[0]=1 root, tree[1]=2 left child, tree[2]=3 right child
println!("left of root: {}", tree[left_child(0)]); // 2
println!("right of root: {}", tree[right_child(0)]); // 3
println!("parent of 6: {}", tree[parent(5)]); // 2
}Operations and Time Complexity
| Operation | Time | Notes |
|---|---|---|
| Insert (level-order, complete tree) | O(n) | BFS to find first open slot |
| Search | O(n) | No ordering: full traversal |
| Delete | O(n) | Find node + restructure |
| Traversal (any) | O(n) | Every node visited once |
| Height | O(n) | Full traversal required |
| Array access (complete tree) | O(1) | Index arithmetic |
Implementation in Rust
use std::collections::VecDeque;
fn inorder(root: &Option<Box<TreeNode>>, result: &mut Vec<i32>) {
if let Some(node) = root {
inorder(&node.left, result);
result.push(node.val);
inorder(&node.right, result);
}
}
fn preorder(root: &Option<Box<TreeNode>>, result: &mut Vec<i32>) {
if let Some(node) = root {
result.push(node.val);
preorder(&node.left, result);
preorder(&node.right, result);
}
}
fn postorder(root: &Option<Box<TreeNode>>, result: &mut Vec<i32>) {
if let Some(node) = root {
postorder(&node.left, result);
postorder(&node.right, result);
result.push(node.val);
}
}
fn level_order(root: &Option<Box<TreeNode>>) -> Vec<Vec<i32>> {
let mut result = Vec::new();
if root.is_none() { return result; }
let mut queue: VecDeque<&TreeNode> = VecDeque::new();
queue.push_back(root.as_ref().unwrap());
while !queue.is_empty() {
let sz = queue.len();
let mut level = Vec::new();
for _ in 0..sz {
let node = queue.pop_front().unwrap();
level.push(node.val);
if let Some(l) = &node.left { queue.push_back(l); }
if let Some(r) = &node.right { queue.push_back(r); }
}
result.push(level);
}
result
}Fundamental Algorithms and Problems
Iterative In-Order Traversal — Stack
Recursive in-order traversal is elegant but uses the call stack. The iterative version explicitly manages a stack. Push nodes while going left; when you can't go further left, pop, visit, then go right. This pattern — push-left, pop-visit, go-right — is the foundation of the BST iterator.
fn inorder_iterative(root: &Option<Box<TreeNode>>) -> Vec<i32> {
let mut result = Vec::new();
let mut stack: Vec<&TreeNode> = Vec::new();
let mut curr: Option<&TreeNode> = root.as_deref();
loop {
// Go as far left as possible
while let Some(node) = curr {
stack.push(node);
curr = node.left.as_deref();
}
match stack.pop() {
None => break,
Some(node) => {
result.push(node.val);
curr = node.right.as_deref();
}
}
}
result
}
fn main() {
let tree = sample_tree();
println!("{:?}", inorder_iterative(&tree)); // [4, 2, 5, 1, 3]
}Maximum and Minimum Depth
Maximum depth is the length of the longest root-to-leaf path. Minimum depth requires care: it is the distance to the nearest leaf, not the nearest null child. A node with only one child should not count as a leaf — only nodes with no children count.
fn max_depth(root: &Option<Box<TreeNode>>) -> i32 {
match root {
None => 0,
Some(node) => 1 + max_depth(&node.left).max(max_depth(&node.right)),
}
}
fn min_depth(root: &Option<Box<TreeNode>>) -> i32 {
match root {
None => 0,
Some(node) => match (&node.left, &node.right) {
(None, None) => 1,
(None, _) => 1 + min_depth(&node.right),
(_, None) => 1 + min_depth(&node.left),
_ => 1 + min_depth(&node.left).min(min_depth(&node.right)),
}
}
}
fn main() {
let tree = sample_tree();
println!("max: {}", max_depth(&tree)); // 3
println!("min: {}", min_depth(&tree)); // 2
}Diameter
The diameter is the longest path between any two nodes — it does not need to pass through the root. At each node, the best diameter through that node is the height of the left subtree plus the height of the right subtree. A single DFS computes both heights and the maximum diameter simultaneously.
fn diameter_helper(root: &Option<Box<TreeNode>>, diameter: &mut i32) -> i32 {
match root {
None => 0,
Some(node) => {
let l = diameter_helper(&node.left, diameter);
let r = diameter_helper(&node.right, diameter);
*diameter = (*diameter).max(l + r); // path through this node
1 + l.max(r) // height returned to parent
}
}
}
fn diameter(root: &Option<Box<TreeNode>>) -> i32 {
let mut d = 0;
diameter_helper(root, &mut d);
d
}
fn main() {
let tree = sample_tree();
println!("diameter: {}", diameter(&tree)); // 4 (4->2->1->3 or 5->2->1->3)
}Path Sum — Root to Leaf
Determine if any root-to-leaf path sums to the target. Subtract the current node's value from the target at each step. At a leaf, check if the remaining target is zero.
fn has_path_sum(root: &Option<Box<TreeNode>>, target: i32) -> bool {
match root {
None => false,
Some(node) => {
let remaining = target - node.val;
if node.left.is_none() && node.right.is_none() {
return remaining == 0;
}
has_path_sum(&node.left, remaining) || has_path_sum(&node.right, remaining)
}
}
}
fn all_paths_sum(root: &Option<Box<TreeNode>>, target: i32, path: &mut Vec<i32>, result: &mut Vec<Vec<i32>>) {
let node = match root { Some(n) => n, None => return };
path.push(node.val);
let remaining = target - node.val;
if node.left.is_none() && node.right.is_none() && remaining == 0 {
result.push(path.clone());
}
all_paths_sum(&node.left, remaining, path, result);
all_paths_sum(&node.right, remaining, path, result);
path.pop(); // backtrack
}
fn main() {
let tree = sample_tree();
println!("{}", has_path_sum(&tree, 7)); // true (1->2->4)
println!("{}", has_path_sum(&tree, 8)); // true (1->2->5)
println!("{}", has_path_sum(&tree, 4)); // true (1->3)
println!("{}", has_path_sum(&tree, 9)); // false
}Symmetric Tree and Invert Binary Tree
A tree is symmetric if it is a mirror image of itself — the left subtree mirrors the right. Check recursively: two nodes mirror each other if their values are equal and each one's left mirrors the other's right.
Inverting swaps every node's left and right children. The recursive solution is a single line: swap, then recurse on both children.
fn is_symmetric(root: &Option<Box<TreeNode>>) -> bool {
fn mirrors(a: &Option<Box<TreeNode>>, b: &Option<Box<TreeNode>>) -> bool {
match (a, b) {
(None, None) => true,
(Some(x), Some(y)) => {
x.val == y.val
&& mirrors(&x.left, &y.right)
&& mirrors(&x.right, &y.left)
}
_ => false,
}
}
match root {
None => true,
Some(node) => mirrors(&node.left, &node.right),
}
}
fn invert(root: Option<Box<TreeNode>>) -> Option<Box<TreeNode>> {
root.map(|mut node| {
let left = invert(node.left.take());
let right = invert(node.right.take());
node.left = right;
node.right = left;
node
})
}
fn main() {
// Symmetric: 1
// / \
// 2 2
// / \ / \
// 3 4 4 3
let mut r = TreeNode::new(1);
let mut l2 = TreeNode::new(2); l2.left = Some(TreeNode::new(3)); l2.right = Some(TreeNode::new(4));
let mut r2 = TreeNode::new(2); r2.left = Some(TreeNode::new(4)); r2.right = Some(TreeNode::new(3));
r.left = Some(l2); r.right = Some(r2);
println!("symmetric: {}", is_symmetric(&Some(r))); // true
}