Tree Terminology Root Leaf Height Depth Level in DSA Rust

Mental Model

A tree is like a family tree where each node has a place, starting from the root and ending at leaves, with height and depth telling how far nodes are from the root or leaves.

Analogy: Imagine a family tree: the oldest ancestor is the root, children are branches, and those with no children are leaves. Height is how tall the tree is from bottom to top, depth is how far a person is from the oldest ancestor, and level is just depth plus one.

        Root (Level 1, Depth 0)
          /      \
     Node1       Node2
     /   \          \
 Leaf1  Leaf2      Leaf3

Legend:
- Root: top ancestor
- Leaf: no children
- Level: distance from root + 1
- Depth: distance from root
- Height: longest path to leaf

Dry Run Walkthrough

Input: Tree with Root node having two children Node1 and Node2; Node1 has two leaves Leaf1 and Leaf2; Node2 has one leaf Leaf3

Goal: Understand and label root, leaves, height, depth, and level for each node

Step 1: Identify the root node

Root (Level 1, Depth 0)
  /      \
Node1    Node2
 /  \       \
L1   L2     L3

Why: Root is the starting point of the tree with no parent

Step 2: Mark leaves as nodes with no children

Root
  /      \
Node1    Node2
 /  \       \
Leaf1 Leaf2  Leaf3 (Leaves)

Why: Leaves are the end points with no further branches

Step 3: Calculate depth for each node from root

Root (Depth 0)
  /          \
Node1 (1)   Node2 (1)
 /    \          \
L1 (2) L2 (2)   L3 (2)

Why: Depth shows how far a node is from the root

Step 4: Calculate level as depth + 1

Root (Level 1)
  /          \
Node1 (2)  Node2 (2)
 /    \          \
L1 (3) L2 (3)   L3 (3)

Why: Level counts nodes starting from 1 at root

Step 5: Calculate height of each node as longest path to a leaf

Root (Height 2)
  /          \
Node1 (1)  Node2 (1)
 /    \          \
L1 (0) L2 (0)   L3 (0)

Why: Height measures how tall the subtree is below each node

Result:

Root (Level 1, Depth 0, Height 2)
  /          \
Node1 (2,1,1) Node2 (2,1,1)
 /    \          \
Leaf1 (3,2,0) Leaf2 (3,2,0) Leaf3 (3,2,0)

Annotated Code

DSA Rust

use std::rc::Rc;
use std::cell::RefCell;

#[derive(Debug)]
struct TreeNode {
    val: String,
    children: Vec<Rc<RefCell<TreeNode>>>,
}

impl TreeNode {
    fn new(val: &str) -> Rc<RefCell<TreeNode>> {
        Rc::new(RefCell::new(TreeNode {
            val: val.to_string(),
            children: vec![],
        }))
    }

    fn height(node: &Rc<RefCell<TreeNode>>) -> usize {
        if node.borrow().children.is_empty() {
            return 0;
        }
        let mut max_child_height = 0;
        for child in node.borrow().children.iter() {
            let h = TreeNode::height(child);
            if h > max_child_height {
                max_child_height = h;
            }
        }
        max_child_height + 1
    }

    fn print_info(node: &Rc<RefCell<TreeNode>>, current_depth: usize) {
        let h = TreeNode::height(node);
        let level = current_depth + 1;
        let is_leaf = node.borrow().children.is_empty();
        println!("{} (Level {}, Depth {}, Height {}, Leaf {})", node.borrow().val, level, current_depth, h, is_leaf);
        for child in node.borrow().children.iter() {
            TreeNode::print_info(child, current_depth + 1);
        }
    }
}

fn main() {
    let root = TreeNode::new("Root");
    let node1 = TreeNode::new("Node1");
    let node2 = TreeNode::new("Node2");
    let leaf1 = TreeNode::new("Leaf1");
    let leaf2 = TreeNode::new("Leaf2");
    let leaf3 = TreeNode::new("Leaf3");

    node1.borrow_mut().children.push(leaf1);
    node1.borrow_mut().children.push(leaf2);
    node2.borrow_mut().children.push(leaf3);

    root.borrow_mut().children.push(node1);
    root.borrow_mut().children.push(node2);

    TreeNode::print_info(&root, 0);
}

fn height(node: &Rc<RefCell<TreeNode>>) -> usize {

recursive function to compute height of subtree rooted at node

if node.borrow().children.is_empty() { return 0; }

base case: leaf nodes have height 0

let mut max_child_height = 0; for child in node.borrow().children.iter() { let h = TreeNode::height(child); if h > max_child_height { max_child_height = h; } }

find maximum height among all children

max_child_height + 1

height is 1 plus max child height

fn print_info(node: &Rc<RefCell<TreeNode>>, current_depth: usize) {

recursive print function that passes depth during traversal

let level = current_depth + 1;

level is always depth + 1

let is_leaf = node.borrow().children.is_empty();

leaf if no children

println!("{} (Level {}, Depth {}, Height {}, Leaf {})", ...);

print all terminology info for the node

TreeNode::print_info(child, current_depth + 1);

recurse on children, incrementing depth

TreeNode::print_info(&root, 0);

initiate traversal from root at depth 0

Output

Root (Level 1, Depth 0, Height 2, Leaf false)

Node1 (Level 2, Depth 1, Height 1, Leaf false)

Leaf1 (Level 3, Depth 2, Height 0, Leaf true)

Leaf2 (Level 3, Depth 2, Height 0, Leaf true)

Node2 (Level 2, Depth 1, Height 1, Leaf false)

Leaf3 (Level 3, Depth 2, Height 0, Leaf true)

Complexity Analysis

Time: O(n) total: print_info traverses each node once, height recursions across all calls visit each node O(1) times

Space: O(h) where h is tree height, due to maximum recursion stack depth in print_info and height

vs Alternative: Iterative BFS/DFS with queue/stack would use O(w) or O(h) space where w is max width; recursion simpler for trees

Edge Cases

Empty tree (no nodes)

No output; main wouldn't create root

DSA Rust

Functions assume valid tree; add checks if needed

Single node tree (only root)

Prints: Root (Level 1, Depth 0, Height 0, Leaf true)

DSA Rust

height returns 0, is_leaf true, depth 0 passed

Tree with one child per node (linear chain)

Depth/level increase linearly, height decreases from root to leaf

DSA Rust

Recursion handles chain up to stack limit

Unbalanced tree (skewed)

Height equals n-1 for chain, recursion depth n

DSA Rust

Rust recursion limit may need increase for very deep trees

When to Use This Pattern

When a problem involves hierarchical data or parent-child relationships, recognize tree terminology to understand node positions and distances.

Common Mistakes

Mistake: Confusing depth and height as the same
Fix: Remember depth is distance from root down, height is distance from node down to farthest leaf

Mistake: Starting level or depth at 0 for root inconsistently
Fix: Standard: depth(root)=0, level(root)=1 or 0 depending on convention; code uses depth 0, level 1

Mistake: Height of leaf as 1
Fix: Convention: height(leaf)=0, number of edges to furthest leaf

Summary

Defines key terms to describe positions and distances in a tree structure.

Use when you need to understand or explain where nodes are in a tree.

Depth counts steps from root down; height counts steps from node down to leaves.

Implemented efficiently in O(n) time using recursive traversal.

Practice

1. In a tree data structure, which node is called the root?

easy

A. The topmost node with no parent

B. Any node with no children

C. A node at the deepest level

D. A node with exactly two children

Solution

1. Step 1: Understand the root node concept

   The root node is the starting point of a tree and has no parent node above it.

2. Step 2: Differentiate root from other nodes

   Leaf nodes have no children, and other nodes may have parents. Only the root has no parent.

3. Final Answer:

   The topmost node with no parent -> Option A

4. Quick Check:

   Root = top node with no parent [OK]

Hint: Root is the node with no parent, always at the top [OK]

Common Mistakes:

• Confusing root with leaf nodes
• Thinking root must have children
• Assuming root is the deepest node

2. Which of the following Rust code snippets correctly defines a leaf node in a binary tree?

easy

A. let leaf = Node { value: 5, left: Some(Box::new(Node)), right: None };

B. struct Node { value: i32, left: Option, right: Option }

C. let leaf = Node { value: 5, left: None, right: None };

D. let leaf = Node { value: 5, left: Some(Box::new(Node)), right: Some(Box::new(Node)) };

Solution

1. Step 1: Identify leaf node properties

   A leaf node has no children, so both left and right must be None.

2. Step 2: Check each option for correct leaf definition

   let leaf = Node { value: 5, left: None, right: None }; sets left and right to None, correctly defining a leaf node.

3. Final Answer:

   let leaf = Node { value: 5, left: None, right: None }; -> Option C

4. Quick Check:

   Leaf node has no children (left and right None) [OK]

Hint: Leaf nodes have left and right as None [OK]

Common Mistakes:

• Setting left or right to Some(Box::new(Node)) for leaf
• Confusing struct definition with instance creation
• Missing Option wrapping for children

3. Given the following tree structure in Rust, what is the depth of node with value 4?

struct Node {
    value: i32,
    left: Option,
    right: Option,
}

let root = Node {
    value: 1,
    left: Some(Box::new(Node {
        value: 2,
        left: Some(Box::new(Node {
            value: 4,
            left: None,
            right: None,
        })),
        right: None,
    })),
    right: Some(Box::new(Node {
        value: 3,
        left: None,
        right: None,
    })),
};

medium

A. 2

B. 0

C. 1

D. 3

Solution

1. Step 1: Understand depth definition

   Depth is the number of edges from the root to the node.

2. Step 2: Trace path from root to node 4

   Path: root(1) -> left(2) -> left(4). Number of edges = 2.

3. Final Answer:

   2 -> Option A

4. Quick Check:

   Depth of node 4 = 2 edges from root [OK]

Hint: Count edges from root to node for depth [OK]

Common Mistakes:

• Counting nodes instead of edges
• Confusing depth with height
• Miscounting path steps

4. The following Rust code attempts to calculate the height of a binary tree node but has a bug. What is the error?

fn height(node: &Option) -> i32 {
    if let Some(n) = node {
        let left_height = height(&n.left);
        let right_height = height(&n.right);
        left_height + right_height + 1
    } else {
        0
    }
}

medium

A. The function should add 2 instead of 1

B. It should return the maximum of left and right heights, not their sum

C. The function should take &Node, not &Option

D. It should return 0 for Some nodes, not null nodes

Solution

1. Step 1: Understand height calculation logic

   Height is the longest path from node to leaf, so use max(left, right) + 1.

2. Step 2: Identify bug in code

   Code adds left_height + right_height + 1, which sums both sides incorrectly.

3. Final Answer:

   It should return the maximum of left and right heights, not their sum -> Option B

4. Quick Check:

   Height = max(left, right) + 1 [OK]

Hint: Height uses max of children heights, not sum [OK]

Common Mistakes:

• Summing left and right heights instead of max
• Confusing height with node count
• Incorrect base case return value

5. You have a tree where the root is at level 0. If a node is at level 3, what is its depth and what is the height of the subtree rooted at this node if it has no children?

hard

A. Depth = 0, Height = 0

B. Depth = 0, Height = 3

C. Depth = 3, Height = 3

D. Depth = 3, Height = 0

Solution

1. Step 1: Understand level and depth relationship

   Level and depth both count edges from root; level 0 means root, so level 3 means depth 3.

2. Step 2: Determine height of leaf node subtree

   A node with no children is a leaf, so its height is 0.

3. Final Answer:

   Depth = 3, Height = 0 -> Option D

4. Quick Check:

   Level = Depth = 3; Leaf height = 0 [OK]

Hint: Leaf node height is 0; level equals depth from root [OK]

Common Mistakes:

• Confusing height with depth
• Assuming leaf height is 1
• Mixing level numbering starting at 1