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.