Tree Terminology Root Leaf Height Depth Level in DSA Rust - Execution Trace

Concept Flow - Tree Terminology Root Leaf Height Depth Level

Start at Root Node

↓

Check if Node has Children?

Yes No↓

Go to Child

↓

Calculate Height & Depth

↓

Assign Level = Depth + 1

↓

Repeat for all Nodes

↓

End Traversal

This flow shows starting from the root node, checking children to identify leaves, calculating height and depth, and assigning levels for all nodes.

Execution Sample

DSA Rust

struct Node {
    value: i32,
    children: Vec<Box<Node>>,
}

// Root is level 1, depth 0
// Leaf has no children
// Height is max distance to leaf

Defines a tree node with children, and notes root, leaf, height, depth, and level concepts.

Execution Table

Step	Current Node	Children?	Depth	Height	Level	Action
1	Root	Yes	0	?	1	Start at root, depth 0, level 1
2	Child A	Yes	1	?	2	Go to child A, depth 1, level 2
3	Child A1	No	2	0	3	Leaf node, height 0, level 3
4	Child A2	No	2	0	3	Leaf node, height 0, level 3
5	Child A	Yes	1	1	2	Height = max child height + 1
6	Child B	No	1	0	2	Leaf node, height 0, level 2
7	Root	Yes	0	2	1	Height = max child height + 1
8	-	-	-	-	-	Traversal complete

💡 Traversal ends after all nodes visited and heights, depths, levels assigned

Variable Tracker

Variable	Start	After Step 1	After Step 2	After Step 3	After Step 4	After Step 5	After Step 6	After Step 7	Final
Current Node	Root	Root	Child A	Child A1	Child A2	Child A	Child B	Root	-
Depth	-	0	1	2	2	1	1	0	-
Height	-	?	?	0	0	1	0	2	-
Level	-	1	2	3	3	2	2	1	-

Key Moments - 3 Insights

Why is the root node's depth 0 but its level 1?

Depth counts edges from root (root has zero edges above), while level counts nodes from root starting at 1. See execution_table steps 1 and 7.

How do we know a node is a leaf?

A leaf node has no children. In the table, steps 3, 4, and 6 show nodes with 'Children?' as No, marking them as leaves.

How is height calculated for non-leaf nodes?

Height is 1 plus the maximum height among its children. Step 5 shows Child A's height as max of its children's heights (0) + 1 = 1.

Visual Quiz - 3 Questions

Look at the execution_table, what is the level of Child A2 at step 4?

A 1

B 2

C 3

D 0

💡 Hint

Check the 'Level' column in execution_table row for step 4.

At which step does the height of the Root node get assigned?

A Step 5

B Step 7

C Step 3

D Step 6

💡 Hint

Look for the row where Current Node is Root and Height is assigned in execution_table.

If Child B had a child node, how would that affect its height in the table?

A Height would be 1 or more

B Depth would become 0

C Height would remain 0

D Level would become 0

💡 Hint

Height depends on children's heights; see how Child A's height changed in step 5.

Concept Snapshot

Tree Terminology Quick Reference:
- Root: top node, depth 0, level 1
- Leaf: node with no children
- Depth: edges from root to node
- Level: depth + 1 (node count from root)
- Height: max edges from node down to leaf
- Height of leaf = 0

Full Transcript

This lesson traces tree terminology by visiting nodes step-by-step. Starting at the root node with depth 0 and level 1, we check if nodes have children. Nodes without children are leaves with height 0. For nodes with children, height is 1 plus the maximum height of their children. Depth counts edges from the root, while level counts nodes starting at 1. The execution table shows each node's depth, height, and level as we traverse. Key moments clarify why root depth is zero but level is one, how leaves are identified, and how height is calculated. The visual quiz tests understanding of these values at specific steps. The snapshot summarizes the key terms and their relationships for quick review.

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