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

Concept Flow - Tree Terminology Root Leaf Height Depth Level

Start at Root Node

↓

Check if Node has Children

Yes No↓

Go to Children

↓

Calculate Height & Depth

↓

Assign Level Based on Depth

↓

Repeat for all Nodes

↓

End

Start from the root node, check children to identify leaves, calculate height and depth, assign levels, and repeat for all nodes.

Execution Sample

DSA C

struct Node {
  int data;
  struct Node* left;
  struct Node* right;
};

Defines a simple binary tree node with data and two children pointers.

Execution Table

Step	Current Node	Is Root?	Is Leaf?	Depth	Height	Level
1	A	Yes	No	0	2	0
2	B	No	No	1	1	1
3	D	No	Yes	2	0	2
4	E	No	Yes	2	0	2
5	C	No	Yes	1	0	1
6	End	-	-	-	-	-

💡 All nodes visited; height and depth calculated; levels assigned.

Variable Tracker

Variable	Start	After Step 1	After Step 2	After Step 3	After Step 4	After Step 5	Final
Current Node	-	A	B	D	E	C	End
Depth	-	0	1	2	2	1	-
Height	-	2	1	0	0	0	-
Level	-	0	1	2	2	1	-

Key Moments - 3 Insights

Why is the root node's depth 0 but its height 2?

Depth counts edges from root to node, so root depth is 0 (step 1). Height counts edges from node to deepest leaf, so root height is 2 because the longest path down has 2 edges (step 1).

How do we know a node is a leaf?

A node is a leaf if it has no children. In the table, nodes D, E, and C have no children and are marked as leaves (steps 3, 4, 5).

What does the level represent and how is it related to depth?

Level equals the depth here (starting from 0 for root), representing the node's position from the root. It is often defined as depth + 1 in some contexts.

Visual Quiz - 3 Questions

Look at the execution_table, what is the height of node B at step 2?

A 0

B 1

C 2

D 3

💡 Hint

Check the 'Height' column at step 2 in execution_table.

At which step does the node become identified as a leaf for the first time?

A Step 3

B Step 2

C Step 1

D Step 5

💡 Hint

Look at the 'Is Leaf?' column in execution_table to find the first 'Yes'.

If the root node had no children, what would its height be?

A 2

B 1

C 0

D Undefined

💡 Hint

Height is number of edges to deepest leaf; no children means height 0.

Concept Snapshot

Tree Terminology Quick Reference:
- Root: top node, depth 0
- Leaf: node with no children
- Depth: edges from root to node
- Height: edges from node to deepest leaf
- Level: often depth + 1 (node position)
Use these to understand tree structure clearly.

Full Transcript

This visual execution traces tree terminology concepts: root, leaf, height, depth, and level. Starting at the root node, we check if nodes have children to identify leaves. Depth counts edges from root to node, height counts edges from node to deepest leaf, and level indicates node position. The execution table shows each node's status step-by-step, tracking depth, height, and level. Key moments clarify common confusions like why root depth is zero but height is not, how leaves are identified, and the meaning of level. The quiz tests understanding by referencing these tracked values. This helps beginners see how tree terms relate in practice.

Practice

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

easy

A. The deepest node in the tree

B. The topmost node with no parent

C. A node with exactly two children

D. Any node with no children

Solution

1. Step 1: Understand the root node definition

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

2. Step 2: Identify the correct node type

   Nodes with no children are called leaves, not root. The root is unique and at the top.

3. Final Answer:

   The topmost node with no parent -> Option B

4. Quick Check:

   Root = topmost node with no parent [OK]

Hint: Root is always the top node without a parent [OK]

Common Mistakes:

• Confusing root with leaf nodes
• Thinking root has children but no parent
• Assuming root is the deepest node

2. Which of the following correctly represents a leaf node in a tree?

easy

A. A node with no children

B. The root node

C. A node with at least one child

D. A node with a parent and children

Solution

1. Step 1: Define a leaf node

   A leaf node is a node that does not have any children nodes connected below it.

2. Step 2: Check options against definition

   Only the option "A node with no children" matches the leaf node definition.

3. Final Answer:

   A node with no children -> Option A

4. Quick Check:

   Leaf = node with no children [OK]

Hint: Leaf nodes have zero children [OK]

Common Mistakes:

• Thinking leaf nodes can have children
• Confusing leaf with root node
• Assuming leaf nodes must have a parent

3. Consider the following tree structure:

        A
       / \
      B   C
     /   / \
    D   E   F

What is the height of node C?

medium

A. 0

B. 2

C. 3

D. 1

Solution

1. Step 1: Understand height of a node

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

2. Step 2: Calculate height of node C

   Node C has children E and F, both leaves (height 0). So height of C = 1 + max(0,0) = 1.

3. Step 3: Verify options

   1 says 1, but height counts edges down, so height is 1. 2 says 2, which is incorrect. Actually, height is 1.

4. Final Answer:

   1 -> Option D

5. Quick Check:

   Height of C = 1 edge to leaf [OK]

Hint: Height counts edges down to farthest leaf [OK]

Common Mistakes:

• Counting nodes instead of edges for height
• Confusing height with depth
• Ignoring that leaves have height 0

4. Given the code snippet below to find the depth of a node in a tree, identify the error:

int depth(Node* root, Node* target) {
    if (root == NULL) return -1;
    if (root == target) return 0;
    int d = depth(root->left, target);
    if (d >= 0) return d + 1;
    d = depth(root->right, target);
    if (d >= 0) return d + 1;
    return -1;
}

medium

A. Function returns -1 when target is root

B. Function does not check both subtrees properly

C. Function correctly calculates depth

D. Function returns depth starting from 1 instead of 0

Solution

1. Step 1: Analyze base cases

   If root is NULL, returns -1 (not found). If root is target, returns 0 (depth zero at root).

2. Step 2: Check recursive calls

   Recursively checks left subtree; if found, adds 1. Else checks right subtree similarly. Returns -1 if not found.

3. Step 3: Confirm correctness

   This correctly calculates depth as number of edges from root to target, starting at 0 for root.

4. Final Answer:

   Function correctly calculates depth -> Option C

5. Quick Check:

   Depth function logic is correct [OK]

Hint: Depth counts edges from root; base case returns 0 [OK]

Common Mistakes:

• Returning wrong base case values
• Not checking both left and right subtrees
• Confusing depth with height

5. In a tree, the level of a node is defined as its depth plus 1. Given the tree below:

        R
       / \
      A   B
     /     \
    C       D
             \
              E

What is the level of node E?

hard

A. 4

B. 3

C. 5

D. 2

Solution

1. Step 1: Find depth of node E

   Depth is number of edges from root R to E. Path: R -> B -> D -> E has 3 edges, so depth = 3.

2. Step 2: Calculate level from depth

   Level = depth + 1 = 3 + 1 = 4.

3. Final Answer:

   4 -> Option A

4. Quick Check:

   Level = depth + 1 = 4 [OK]

Hint: Level = depth + 1, count edges then add one [OK]

Common Mistakes:

• Counting nodes instead of edges for depth
• Forgetting to add 1 for level
• Confusing level with height