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

Concept Flow - Tree Terminology Root Leaf Height Depth Level

Start at Root Node

↓

Check if Node has Children?

No→Leaf Node

Yes↓

Move to Child Node

↓

Calculate Depth and Level

↓

Calculate Height from Leaf Upwards

↓

Repeat for all Nodes

↓

End

This flow shows how we start from the root, check children to find leaves, calculate depth and level going down, and height going up.

Execution Sample

DSA Go

type Node struct {
  Value int
  Children []*Node
}

// Root is the top node
// Leaf has no children
// Depth counts edges from root
// Height counts edges to deepest leaf
// Level = Depth + 1

Defines a tree node and explains root, leaf, depth, height, and level concepts.

Execution Table

Step	Current Node	Children?	Depth	Level	Height	Action
1	Root	Yes (2 children)	0	1	?	Start at root node
2	Child A	Yes (1 child)	1	2	?	Move to Child A
3	Child A1	No	2	3	0	Leaf node found, height=0
4	Child A	Yes	1	2	1	Height = 1 + max child height (0)
5	Child B	No	1	2	0	Leaf node found, height=0
6	Root	Yes	0	1	2	Height = 1 + max child height (1)
7	-	-	-	-	-	Traversal complete

💡 All nodes visited, heights and depths calculated

Variable Tracker

Variable	Start	After Step 2	After Step 4	After Step 6	Final
Current Node	Root	Child A	Child A	Root	-
Depth	0	1	1	0	-
Level	1	2	2	1	-
Height	?	?	1	2	-

Key Moments - 3 Insights

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

Depth counts edges from root, so root has 0 edges above it. Level counts nodes from root, so root is level 1. See execution_table rows 1 and 6.

How do we know a node is a leaf?

A leaf has no children. In execution_table row 3 and 5, nodes with no children are leaves with height 0.

How is height calculated for non-leaf nodes?

Height is 1 plus the maximum height of its children. See row 4 where Child A's height is 1 + 0 from Child A1.

Visual Quiz - 3 Questions

Look at the execution_table, what is the height of Child B at step 5?

A 2

B 0

C 1

D Undefined

💡 Hint

Check the 'Height' column at step 5 in execution_table

At which step does the depth become 2?

A Step 1

B Step 5

C Step 3

D Step 6

💡 Hint

Look at the 'Depth' column in execution_table rows

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

A 0

B 1

C Undefined

D Same as depth

💡 Hint

Height of leaf nodes (no children) is 0, see rows 3 and 5

Concept Snapshot

Tree Terminology:
- Root: top node, depth=0, level=1
- Leaf: node with no children, height=0
- Depth: edges from root to node
- Level: depth + 1
- Height: edges from node down to deepest leaf
Calculate depth going down, height going up.

Full Transcript

This lesson shows tree terms: root, leaf, depth, height, and level. We start at the root node with depth 0 and level 1. We move down children, increasing depth and level. Leaves have no children and height 0. Height of other nodes is 1 plus max height of children. The execution table traces each step, showing current node, children, depth, level, and height. Key moments clarify why root depth is zero but level one, how to identify leaves, and how height is calculated. The quiz tests understanding of height, depth, and leaf nodes. This helps visualize tree structure clearly.