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

Concept Flow - Tree Terminology Root Leaf Height Depth Level

Start: Tree Structure

↓

Identify Root Node

↓

Traverse to Leaves

↓

Calculate Height

↓

Calculate Depth

↓

Determine Level

↓

End: Understand Tree Terms

This flow shows how to identify key parts of a tree and calculate height, depth, and level step-by-step.

Execution Sample

DSA C++

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

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

Execution Table

Step	Action	Node	Height	Depth	Level	Description
1	Identify Root	A	?	0	1	Root node A has depth 0 and level 1
2	Go to Left Child	B	?	1	2	Node B is child of A, depth 1, level 2
3	Go to Left Child	D	0	2	3	Node D is leaf, height 0, depth 2, level 3
4	Go to Right Child	E	0	2	3	Node E is leaf, height 0, depth 2, level 3
5	Calculate Height	B	1	1	2	Height of B is max height of children +1 = 1
6	Go to Right Child	C	?	1	2	Node C is child of A, depth 1, level 2
7	Go to Right Child	F	0	2	3	Node F is leaf, height 0, depth 2, level 3
8	Calculate Height	C	1	1	2	Height of C is max height of children +1 = 1
9	Calculate Height	A	2	0	1	Height of root A is max height of B and C +1 = 2
10	End	-	-	-	-	All nodes processed with height, depth, and level assigned

💡 Traversal complete; all nodes have height, depth, and level calculated.

Variable Tracker

Variable	Start	After Step 1	After Step 2	After Step 3	After Step 5	After Step 6	After Step 8	After Step 9	Final
Node	None	A	B	D	B	C	C	A	All nodes
Height	?	?	?	0	1	?	1	2	A=2,B=1,C=1,D=0,E=0,F=0
Depth	?	0	1	2	1	1	1	0	A=0,B=1,C=1,D=2,E=2,F=2
Level	?	1	2	3	2	2	2	1	A=1,B=2,C=2,D=3,E=3,F=3

Key Moments - 3 Insights

Why is the root node depth 0 but level 1?

Depth counts edges from root to node, so root has 0 edges to itself. Level counts nodes from root starting at 1, so root is level 1. See execution_table steps 1 and variable_tracker for depth and level values.

How is height calculated for leaf nodes?

Leaf nodes have no children, so their height is 0 by definition. This is shown in execution_table steps 3 and 4 where nodes D and E have height 0.

Why does height of a node depend on its children?

Height is the longest path down to a leaf. So height of a node is max height of its children plus 1. See execution_table steps 5, 8, and 9 for height calculations.

Visual Quiz - 3 Questions

Look at the execution_table at step 3, what is the height of node D?

A 0

B 1

C 2

D Undefined

💡 Hint

Check the Height column at step 3 in execution_table.

At which step does the height of the root node A get calculated?

A Step 8

B Step 9

C Step 5

D Step 10

💡 Hint

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

If node C had an extra child with height 2, how would that affect the height of node A?

A Height of A stays 2

B Height of A becomes 1

C Height of A becomes 3

D Height of A becomes 4

💡 Hint

Height of a node is max height of children plus 1, see execution_table steps 5, 8, 9.

Concept Snapshot

Tree Terminology Quick Reference:
- Root: Top node, depth 0, level 1
- Leaf: Node with no children, height 0
- Height: Longest path down to leaf
- Depth: Edges from root to node
- Level: Depth + 1 (nodes count from root)
Use these to understand tree structure clearly.

Full Transcript

This lesson shows how to identify and calculate key tree terms: root, leaf, height, depth, and level. We start by identifying the root node with depth 0 and level 1. Then we traverse children nodes, assigning depth as edges from root and level as depth plus one. Leaf nodes have height zero because they have no children. Height of other nodes is calculated as one plus the maximum height of their children. The execution table traces these values step-by-step for each node. Key moments clarify common confusions about root depth vs level and height calculation. Visual quizzes test understanding by referencing the execution table and variable tracker. The snapshot summarizes the terms for quick recall.

Practice

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

easy

A. A node with exactly two children

B. A node with no children

C. The topmost node with no parent

D. Any node at the bottom level

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, but root has no parent. Bottom level nodes are leaves or internal nodes, not necessarily root.

3. Final Answer:

   The topmost node with no parent -> Option C

4. Quick Check:

   Root = topmost node with no parent [OK]

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

Common Mistakes:

• Confusing root with leaf node
• Thinking root must have children
• Assuming root is at bottom level

2. Which of the following is the correct way to declare a simple binary tree node struct in C++?

easy

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

B. struct Node { int data; Node left; Node right; };

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

D. struct Node { int data; int left; int right; };

Solution

1. Step 1: Check pointer usage for child nodes

   Child nodes must be pointers to Node to allow recursive structure.

2. Step 2: Validate data types of members

   Data is int, left and right are pointers to Node, so struct Node { int data; Node* left; Node* right; }; is correct.

3. Final Answer:

   struct Node { int data; Node* left; Node* right; }; -> Option A

4. Quick Check:

   Child nodes use pointers in struct [OK]

Hint: Child nodes must be pointers to Node type [OK]

Common Mistakes:

• Using Node instead of Node* for children
• Mixing int and Node types for children
• Missing semicolon at struct end

3. Consider the following tree:

        10
       /  \
      5    15
     /    /  \
    3    12  20

What is the height of the node with value 5?

medium

A. 1

B. 2

C. 3

D. 0

Solution

1. Step 1: Understand height definition

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

2. Step 2: Calculate height of node 5

   Node 5 has left child 3 (leaf). Longest path from 5 to leaf is 5 -> 3, which is 1 edge. Height of 3 is 0. Height of 5 = 1 + max height of children = 1 + 0 = 1. However, node 5 has no right child, so max height is 1. So height is 1. But the question asks for height of node 5. Since 3 is leaf (height 0), height of 5 is 1. But 2 says 2, which is incorrect. So correct answer is 1 (1).

3. Final Answer:

   1 -> Option A

4. Quick Check:

   Height = edges to deepest leaf = 1 [OK]

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

Common Mistakes:

• Counting nodes instead of edges
• Confusing height with depth
• Ignoring missing right child

4. Given the following code snippet, what is the error?

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

Node* root = new Node{10, nullptr, nullptr};
root->left = new Node{5, nullptr, nullptr};
root->left->left = new Node{3, nullptr, nullptr};
root->right = new Node{15, nullptr, nullptr};
root->right->right = new Node{20, nullptr, nullptr};
root->right->left = 12;

medium

A. Incorrect initialization of root node

B. Missing semicolon after struct definition

C. Using nullptr instead of NULL

D. Assigning int 12 to a Node* pointer

Solution

1. Step 1: Analyze the last assignment

   Line root->right->left = 12; assigns integer 12 to a pointer Node* left, which is invalid.

2. Step 2: Check pointer assignment rules

   Pointers must be assigned addresses or nullptr, not raw integers.

3. Final Answer:

   Assigning int 12 to a Node* pointer -> Option D

4. Quick Check:

   Pointer must hold address, not int [OK]

Hint: Pointers cannot hold raw integers [OK]

Common Mistakes:

• Ignoring type mismatch in assignment
• Thinking nullptr and NULL difference causes error
• Overlooking semicolon presence

5. In a tree, the depth of a node is defined as the number of edges from the root to that node. Given the tree:

        1
       / \
      2   3
     /   / \
    4   5   6
       /
      7

What is the depth of node 7 and what is its level?

hard

A. Depth = 3, Level = 3

B. Depth = 3, Level = 4

C. Depth = 4, Level = 3

D. Depth = 4, Level = 4

Solution

1. Step 1: Calculate depth of node 7

   Path from root (1) to 7 is 1 -> 3 -> 5 -> 7, which has 3 edges, so depth = 3.

2. Step 2: Calculate level of node 7

   Level is depth + 1, so level = 3 + 1 = 4.

3. Final Answer:

   Depth = 3, Level = 4 -> Option B

4. Quick Check:

   Level = depth + 1 = 4 [OK]

Hint: Level = depth + 1 always [OK]

Common Mistakes:

• Confusing depth with level
• Counting nodes instead of edges for depth
• Starting depth count from 0 or 1 incorrectly