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

Concept Flow - Tree Terminology Root Leaf Height Depth Level

Start: Tree

↓

Identify Root Node

↓

Traverse to Children

↓

Check if Node is Leaf

↓

Leaf Node

↓

Calculate Depth & Level

↓

Calculate Height

↓

End

This flow shows how to identify root, leaf nodes, and calculate height, depth, and level in a tree.

Execution Sample

DSA C#

class Node {
  public int Value;
  public Node Left, Right;
  public Node(int val) { Value = val; }
}

Defines a simple tree node with value and left/right children.

Execution Table

Step	Action	Node	Is Root?	Is Leaf?	Depth	Level	Height
1	Start at root	10	Yes	No	0	1	3
2	Go to left child	5	No	No	1	2	1
3	Go to left child	3	No	Yes	2	3	0
4	Back to 5, go to right child	7	No	Yes	2	3	0
5	Back to root, go to right child	15	No	No	1	2	2
6	Go to right child	18	No	Yes	2	3	0
7	Calculate height of 15	15	No	No	1	2	2
8	Calculate height of root	10	Yes	No	0	1	3
9	End traversal	-	-	-	-	-	-

💡 Traversal ends after visiting all nodes and calculating height, depth, and level.

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	After Step 8	Final
Current Node	null	10	5	3	7	15	18	15	10	null
Is Root?	false	true	false	false	false	false	false	false	true	false
Is Leaf?	false	false	false	true	true	false	true	false	false	false
Depth	-	0	1	2	2	1	2	1	0	-
Level	-	1	2	3	3	2	3	2	1	-
Height	-	3	1	0	0	2	0	2	3	-

Key Moments - 3 Insights

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

Depth counts edges from root (0 for root), level counts nodes from root (1 for root). See execution_table steps 1 and 8.

How do we know a node is a leaf?

A leaf has no children. In execution_table steps 3,4,6, nodes 3,7,18 have no children and are marked leaf.

What does height represent and how is it calculated?

Height is the longest path from a node down to a leaf. Calculated bottom-up as in steps 7 and 8.

Visual Quiz - 3 Questions

Look at the execution_table, what is the depth of node 7 at step 4?

A 1

B 2

C 3

D 0

💡 Hint

Check the 'Depth' column at step 4 in execution_table.

At which step does the traversal visit the right child of the root node?

A Step 5

B Step 3

C Step 2

D Step 6

💡 Hint

Look for action 'Back to root, go to right child' in execution_table.

If node 18 had a child, how would its 'Is Leaf?' value change at step 6?

A It would become 'Root'

B It would remain 'Yes'

C It would change to 'No'

D It would be 'Unknown'

💡 Hint

Leaf means no children; adding a child changes 'Is Leaf?' to 'No'. See step 6.

Concept Snapshot

Tree Terms:
- Root: top node, depth=0, level=1
- Leaf: node with no children
- Depth: edges from root to node
- Level: nodes count from root (root=1)
- Height: longest path from node down to leaf

Full Transcript

This lesson shows how to identify root and leaf nodes in a tree and how to calculate depth, level, and height. The root node is the top node with depth zero and level one. Leaf nodes have no children. Depth counts edges from root to a node, while level counts nodes starting at one for the root. Height is the longest path from a node down to a leaf. The execution table traces visiting nodes, checking if they are root or leaf, and calculating depth, level, and height step-by-step.

Practice

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

easy

A. The topmost node with no parent

B. A node with no children

C. Any node at the bottom 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: Identify the correct description

   Among the options, only the topmost node with no parent matches the root node definition.

3. Final Answer:

   The topmost node with no parent -> Option A

4. Quick Check:

   Root = topmost node with no parent [OK]

Hint: Root is the very first node without a parent [OK]

Common Mistakes:

• Confusing root with leaf nodes
• Thinking root must have children
• Assuming root is any node at the bottom

2. Which of the following is the correct way to declare a simple tree node class in C# with a value and children list?

easy

A. class Node { int Value; int Children; }

B. class Node { public int Value; public Node Children; }

C. class Node { public int Value; public List<Node> Children; }

D. class Node { public int Value; public Node[] Children; }

Solution

1. Step 1: Check for correct data types and access modifiers

   The node should have a public integer value and a list of child nodes. class Node { public int Value; public List<Node> Children; } uses List<Node> which is correct.

2. Step 2: Eliminate incorrect options

   class Node { int Value; int Children; } uses int for children which is wrong. class Node { public int Value; public Node Children; } uses a single Node for children instead of a list. class Node { public int Value; public Node[] Children; } uses an array which is valid but less flexible than List.

3. Final Answer:

   class Node { public int Value; public List<Node> Children; } -> Option C

4. Quick Check:

   Use List<Node> for children in C# [OK]

Hint: Use List<Node> for multiple children in C# [OK]

Common Mistakes:

• Using int instead of List<Node> for children
• Missing public access modifier
• Using single Node instead of collection for children

3. Given a tree where the root is at level 0, what is the level of a leaf node that is 4 edges away from the root?

easy

A. 3

B. 4

C. 5

D. 6

Solution

1. Step 1: Understand level definition

   Level of a node is the number of edges from the root to that node, starting at 0 for root.

2. Step 2: Calculate leaf node level

   If leaf is 4 edges away from root, its level is 4.

3. Final Answer:

   4 -> Option B

4. Quick Check:

   Level = edges from root = 4 [OK]

Hint: Level equals number of edges from root [OK]

Common Mistakes:

• Confusing level with height
• Starting level count at 1 instead of 0
• Mixing depth and level definitions

4. Consider the following tree structure:

Node root = new Node { Value = 1, Children = new List<Node> {
  new Node { Value = 2, Children = new List<Node> {
    new Node { Value = 4, Children = new List<Node>() },
    new Node { Value = 5, Children = new List<Node>() }
  }},
  new Node { Value = 3, Children = new List<Node>() }
}};

What is the height of this tree?

medium

A. 2

B. 3

C. 1

D. 4

Solution

1. Step 1: Understand height definition

   Height is the number of edges on the longest path from the root to a leaf node.

2. Step 2: Trace the longest path in the tree

   Longest path: root(1) -> 2 -> 4 (or 5). This path has 2 edges, so height = 2.

3. Step 3: Reconsider height counting

   Height is often defined as the number of nodes on the longest path minus 1, which equals the number of edges. The path has 3 nodes (1,2,4), so height = 2 edges, which is correct. However, some definitions count height as number of nodes, which would be 3.

4. Step 4: Confirm standard definition

   Standard definition: height = number of edges = 2.

5. Final Answer:

   2 -> Option A

6. Quick Check:

   Height = longest path edges = 2 [OK]

Hint: Height = number of edges on longest root-to-leaf path [OK]

Common Mistakes:

• Counting nodes instead of edges for height
• Confusing height with depth
• Ignoring leaf nodes at bottom

5. The following code tries to calculate the depth of a node in a tree but has a bug:

int GetDepth(Node node) {
  if (node == null) return 0;
  return 1 + GetDepth(node.Children[0]);
}

What is the main problem with this code?

medium

A. It causes infinite recursion for leaf nodes

B. It returns 0 for null nodes instead of -1

C. It does not handle the root node correctly

D. It only checks the first child, ignoring others

Solution

1. Step 1: Analyze recursion logic

   The function calls itself only on the first child (Children[0]), ignoring other children.

2. Step 2: Identify the bug impact

   This means it does not calculate depth correctly if node has multiple children; it misses deeper paths.

3. Final Answer:

   It only checks the first child, ignoring others -> Option D

4. Quick Check:

   Check all children for correct depth [OK]

Hint: Check all children, not just first, when calculating depth [OK]

Common Mistakes:

• Assuming single child trees only
• Ignoring null checks for children list
• Confusing depth with height