Height and depth of trees in Data Structures Theory - Step-by-Step Execution

Concept Flow - Height and depth of trees

Start at Root Node

↓

Depth of Root = 0

↓

Move to Child Node

↓

Depth of Child = Depth of Parent + 1

↓

Repeat for all nodes

↓

Calculate Height

↓

Height = Max Depth among all nodes

↓

End

Start from the root node with depth 0, move down each child increasing depth by 1, and find the height as the maximum depth found.

Execution Sample

Data Structures Theory

Node A (root)
  |
  +-- Node B
  |     |
  |     +-- Node D
  +-- Node C
        |
        +-- Node E

A tree with root A, children B and C, and further children D and E to show depth and height.

Analysis Table

Step	Current Node	Depth	Action	Height So Far
1	A (root)	0	Start at root	0
2	B	1	Move to child of A	0
3	D	2	Move to child of B	0
4	Back to B	1	No more children	2
5	Back to A	0	Move to next child	2
6	C	1	Move to child of A	2
7	E	2	Move to child of C	2
8	Back to C	1	No more children	2
9	Back to A	0	No more children	2
10	-	-	Traversal complete	Height = 2

💡 All nodes visited; maximum depth found is 2, so height is 2.

State Tracker

Variable	Start	After Step 2	After Step 3	After Step 7	Final
Current Node	A	B	D	E	-
Depth	0	1	2	2	-
Height So Far	0	0	0	2	2

Key Insights - 3 Insights

Why is the root node depth 0 and not 1?

Depth counts edges from root to node. Root has no edges above it, so depth is 0 (see Step 1 in execution_table).

How is height different from depth?

Depth is distance from root to a node; height is the longest depth among all nodes (see Height So Far column in execution_table).

Why does height update only after visiting leaf nodes?

Height depends on maximum depth found, which is known after reaching leaves (see Steps 4 and 7 where height updates to 2).

Visual Quiz - 3 Questions

Look at the execution_table at Step 3. What is the depth of node D?

A 2

B 1

C 0

D 3

💡 Hint

Check the Depth column at Step 3 in execution_table.

At which step does the height first update to 2?

A Step 2

B Step 7

C Step 4

D Step 9

💡 Hint

Look at the Height So Far column in execution_table rows.

If node E had a child node F, how would the final height change?

A Height would remain 2

B Height would become 3

C Height would become 1

D Height would become 4

💡 Hint

Height is maximum depth; adding a child to E increases max depth by 1 (see variable_tracker Depth values).

Concept Snapshot

Height and Depth of Trees:
- Depth: number of edges from root to a node (root depth = 0)
- Height: maximum depth among all nodes
- Calculate depth by adding 1 moving down each level
- Height is found after visiting all nodes
- Useful for understanding tree structure size

Full Transcript

This visual execution shows how to find the depth and height of a tree. Starting at the root node with depth zero, we move down each child node, increasing depth by one each time. We track the current node and its depth step-by-step. The height is the maximum depth found after visiting all nodes. For example, node D and node E have depth 2, so the height is 2. The root node has depth zero because it has no edges above it. Height updates after reaching leaf nodes, as shown in the execution table. If a new child is added deeper in the tree, the height increases accordingly.

Practice

1. What does the depth of a node in a tree represent?

easy

A. The number of edges from the root to that node

B. The number of edges from that node to the farthest leaf

C. The total number of nodes in the tree

D. The number of children the node has

Solution

1. Step 1: Understand the definition of depth

   Depth is defined as the distance from the root node to the given node, measured in edges.

2. Step 2: Compare with other options

   Height measures distance to farthest leaf, not depth. Total nodes and children count are unrelated.

3. Final Answer:

   The number of edges from the root to that node -> Option A

4. Quick Check:

   Depth = edges from root to node [OK]

Hint: Depth counts edges from root down to the node [OK]

Common Mistakes:

• Confusing depth with height
• Thinking depth counts children
• Mixing depth with total nodes

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

easy

A. Height is always 1

B. Height is 0 because it has no children

C. Height equals the depth of the leaf

D. Height is the number of siblings it has

Solution

1. Step 1: Recall height definition for any node

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

2. Step 2: Apply to leaf node

   A leaf node has no children, so the longest path down is zero edges, making height 0.

3. Final Answer:

   Height is 0 because it has no children -> Option B

4. Quick Check:

   Leaf height = 0 edges down [OK]

Hint: Leaf nodes always have height zero [OK]

Common Mistakes:

• Assuming height is 1 for leaves
• Confusing height with depth
• Counting siblings as height

3. Consider the following tree structure:

        A
       / \
      B   C
     /   / \
    D   E   F
           /
          G

What is the height of node C?

medium

A. 0

B. 1

C. 3

D. 2

Solution

1. Step 1: Identify the subtree rooted at node C

   Node C has children E and F; F has child G.

2. Step 2: Find longest path from C down to a leaf

   Paths: C->E (1 edge), C->F->G (2 edges). Longest path length is 2 edges.

3. Final Answer:

   2 -> Option D

4. Quick Check:

   Height of C = longest path down = 2 edges [OK]

Hint: Height = longest edges down from node [OK]

Common Mistakes:

• Counting number of children instead of edges
• Confusing height with depth
• Ignoring deeper descendants

4. A student wrote that the depth of the root node in any tree is 1. What is wrong with this statement?

medium

A. Depth depends on number of children, not fixed

B. Depth of root is always equal to height

C. Depth of root is always 0, not 1

D. Depth cannot be defined for root node

Solution

1. Step 1: Recall definition of depth for root

   Depth is edges from root to node; root is at distance zero from itself.

2. Step 2: Identify error in student's statement

   Student incorrectly assigns depth 1 to root; correct depth is 0.

3. Final Answer:

   Depth of root is always 0, not 1 -> Option C

4. Quick Check:

   Root depth = 0 edges [OK]

Hint: Root node depth is zero by definition [OK]

Common Mistakes:

• Assigning depth 1 to root
• Confusing depth with height
• Thinking depth depends on children

5. Given a tree where the root node has depth 0 and height 4, and a node at depth 3 has height 1, what is the height of a leaf node at depth 4?

hard

A. 0

B. 1

C. 3

D. 4

Solution

1. Step 1: Understand height of leaf nodes

   Leaf nodes have height 0 because they have no children below.

2. Step 2: Apply to leaf at depth 4

   Since the node at depth 3 has height 1, its child at depth 4 must be a leaf with height 0.

3. Final Answer:

   0 -> Option A

4. Quick Check:

   Leaf node height = 0 [OK]

Hint: Leaf nodes always have height zero regardless of depth [OK]

Common Mistakes:

• Assuming height equals depth
• Thinking height increases with depth
• Confusing height with number of siblings