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.

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 lowest level

D. A node with exactly two children

Solution

1. Step 1: Understand the root node definition

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

3. Final Answer:

   The topmost node with no parent -> Option A

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 node
• Thinking root must have children
• Assuming root is at the lowest level

2. Which of the following is the correct way to declare a tree node struct in Go with integer data and pointers to left and right children?

easy

A. type Node struct { data int, left &Node, right &Node }

B. type Node struct { data int, left *Node, right *Node }

C. type Node struct { data int, left Node, right Node }

D. type Node struct { data int, left Node*, right Node* }

Solution

1. Step 1: Recall Go pointer syntax

   In Go, pointers are declared with * before the type, e.g., *Node.

2. Step 2: Check each option's pointer usage

   type Node struct { data int, left *Node, right *Node } uses *Node correctly. type Node struct { data int, left Node, right Node } uses Node (value, not pointer). type Node struct { data int, left &Node, right &Node } uses &Node which is invalid syntax. type Node struct { data int, left Node*, right Node* } uses Node* which is invalid in Go.

3. Final Answer:

   type Node struct { data int, left *Node, right *Node } -> Option B

4. Quick Check:

   Pointer syntax in Go = *Type [OK]

Hint: Use *Type for pointers in Go structs [OK]

Common Mistakes:

• Using value type instead of pointer for children
• Using &Type or Type* which are invalid in Go
• Using semicolons instead of commas in struct fields

3. Given the following tree structure in Go, what is the depth of node with value 5?

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

root := &Node{data: 1}
root.left = &Node{data: 2}
root.right = &Node{data: 3}
root.left.left = &Node{data: 4}
root.left.right = &Node{data: 5}

medium

A. 2

B. 1

C. 3

D. 4

Solution

1. Step 1: Understand depth definition

   Depth of a node is the number of edges from the root to that node.

2. Step 2: Trace path from root to node 5

   Path: 1 (root) -> 2 -> 5. Number of edges = 2.

3. Final Answer:

   2 -> Option A

4. Quick Check:

   Depth = edges from root = 2 [OK]

Hint: Count edges from root to node for depth [OK]

Common Mistakes:

• Counting nodes instead of edges
• Confusing depth with height
• Miscounting path length

4. Consider this Go code snippet for a binary tree node:

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

func isLeaf(n *Node) bool {
  return n.left == nil && n.right == nil
}

root := &Node{data: 10}
root.left = &Node{data: 20}
root.right = &Node{data: 30}
root.left.left = &Node{data: 40}

fmt.Println(isLeaf(root.left))

What is the output and why?

medium

A. true

B. Runtime panic

C. Compilation error

D. false

Solution

1. Step 1: Understand isLeaf function

   It returns true if both left and right children are nil (no children).

2. Step 2: Check root.left node children

   root.left has left child (40) but no right child, so left != nil, right == nil.

3. Step 3: Evaluate isLeaf(root.left)

   Since left is not nil, isLeaf returns false.

4. Final Answer:

   false -> Option D

5. Quick Check:

   Leaf = no children, root.left has left child [OK]

Hint: Leaf nodes have no children; check both left and right nil [OK]

Common Mistakes:

• Assuming node with one child is leaf
• Confusing nil checks causing panic
• Expecting true without checking both children

5. You have a binary tree where the root is at level 0. If a node is at level 3, what is its height assuming the tree height is 5? Also, which node is at level 0? Choose the correct pair of answers.

hard

A. Height = 5; Root node is at level 0

B. Height = 3; Leaf node is at level 0

C. Height = 2; Root node is at level 0

D. Height = 2; Leaf node is at level 0

Solution

1. Step 1: Calculate height of node at level 3

   Height = total tree height - node level = 5 - 3 = 2.

2. Step 2: Identify node at level 0

   By definition, root node is at level 0.

3. Final Answer:

   Height = 2; Root node is at level 0 -> Option C

4. Quick Check:

   Height = 5 - 3 = 2; Root at level 0 [OK]

Hint: Height = tree height - level; root always level 0 [OK]

Common Mistakes:

• Confusing height with level
• Assuming leaf node at level 0
• Calculating height as level number