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

Concept Flow - Tree Terminology Root Leaf Height Depth Level

Start at Root Node

↓

Check if Node has Children?

Yes No↓

Go to Child

↓

Calculate Height & Depth

↓

Assign Level Based on Depth

↓

End Traversal

This flow shows starting from the root, checking children to find leaves, calculating height and depth, and assigning levels.

Execution Sample

DSA Python

class Node:
    def __init__(self, val):
        self.val = val
        self.children = []

root = Node(1)
root.children = [Node(2), Node(3)]

Creates a simple tree with root node 1 and two children nodes 2 and 3.

Execution Table

Step	Current Node	Is Root?	Has Children?	Is Leaf?	Depth	Height	Level
1	Node 1	Yes	Yes	No	0	1	0
2	Node 2	No	No	Yes	1	0	1
3	Node 3	No	No	Yes	1	0	1
4	Traversal Complete	-	-	-	-	-	-

💡 Traversal ends after visiting all nodes and calculating their properties.

Variable Tracker

Variable	Start	After Step 1	After Step 2	After Step 3	Final
Current Node	null	Node 1	Node 2	Node 3	Traversal Complete
Depth	-	0	1	1	-
Height	-	1	0	0	-
Level	-	0	1	1	-

Key Moments - 3 Insights

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

Depth counts edges from root to node, so root depth is 0 (no edges). Height counts edges from node to deepest leaf, so root height is 1 because the longest path down has 1 edge (to leaves). See execution_table steps 1 and 2.

Why are nodes 2 and 3 considered leaves?

Because they have no children (Has Children? is No), so they are leaves. This is shown in execution_table steps 2 and 3.

How is level related to depth?

Level is the same as depth here, representing how far the node is from the root. For example, root level is 0, children level is 1 (execution_table).

Visual Quiz - 3 Questions

Look at the execution_table, what is the height of Node 1 at step 1?

A 0

B 2

C 1

D -

💡 Hint

Check the 'Height' column in execution_table row for step 1.

At which step does the node become a leaf?

A Step 1

B Step 2

C Step 4

D Step 3

💡 Hint

Look at the 'Is Leaf?' column in execution_table for steps 2 and 3.

If Node 3 had a child, how would its 'Is Leaf?' value change at step 3?

A No

B Yes

C '-' (unknown)

D Yes, but only if child is leaf

💡 Hint

A node with children is not a leaf; see 'Has Children?' and 'Is Leaf?' columns.

Concept Snapshot

Tree Terminology Quick Reference:
- Root: The top node, depth 0.
- Leaf: Node with no children.
- Depth: Edges from root to node.
- Height: Edges from node to deepest leaf.
- Level: Same as depth, node's distance from root.

Full Transcript

This lesson shows how to identify root, leaf nodes, and calculate height, depth, and level in a tree. Starting from the root node, we check if nodes have children. Nodes without children are leaves. Depth is how far a node is from the root, counting edges. Height is how far the deepest leaf is from the node. Level matches depth, showing node's position in the tree. The example tree has root node 1 with two children nodes 2 and 3, both leaves. Root depth is 0, height is 1. Children depth and level are 1, height 0.

Practice

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

easy

A. A node at the lowest level

B. The topmost node with no parent

C. Any node with no children

D. A node with exactly two children

Solution

1. Step 1: Understand the root node definition

   The root node is the starting point of the tree and has no parent node above it.

2. Step 2: Compare options with definition

   The topmost node with no parent matches this definition exactly. Other options describe leaf nodes or other properties.

3. Final Answer:

   The topmost node with no parent -> Option B

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 has children always
• Mixing root with internal nodes

2. Which of the following is the correct way to represent the leaf node in a tree?

easy

A. A node with no children

B. A node with exactly one child

C. The root node

D. A node with at least one child

Solution

1. Step 1: Define leaf node

   A leaf node is a node that has no children; it is at the end of a branch.

2. Step 2: Match definition with options

   A node with no children states a node with no children, which matches the leaf node definition.

3. Final Answer:

   A node with no children -> Option A

4. Quick Check:

   Leaf = node with no children [OK]

Hint: Leaf nodes have zero children [OK]

Common Mistakes:

• Thinking leaf nodes have children
• Confusing leaf with root
• Assuming leaf nodes must have one child

3. Consider the following tree structure:

       A
      / \
     B   C
    /   / \
   D   E   F

What is the height of node C?

medium

A. 0

B. 2

C. 3

D. 1

Solution

1. Step 1: Understand height of a node

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

2. Step 2: Calculate height of node C

   Node C has children E and F, both leaves with height 0. So height of C = 1 + max(0,0) = 1.

3. Step 3: Verify options

   1 says 1, but height counts edges down, so height is 1. 2 says 2, which is incorrect. 0 is 0, which is leaf height.

4. Final Answer:

   1 -> Option D

5. Quick Check:

   Height of C = 1 edge to leaf [OK]

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

Common Mistakes:

• Confusing height with depth
• Counting nodes instead of edges
• Assuming leaf height is 1

4. Given the tree below:

       X
      / \
     Y   Z
    / 
   W  

What is the depth of node W?
Note: Depth is the number of edges from the root to the node.

medium

A. 2

B. 1

C. 0

D. 3

Solution

1. Step 1: Understand depth definition

   Depth is the number of edges from the root node to the target node.

2. Step 2: Trace path from root to W

   Path: X (root) -> Y -> W. Number of edges = 2.

3. Final Answer:

   2 -> Option A

4. Quick Check:

   Depth of W = 2 edges from root [OK]

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

Common Mistakes:

• Counting nodes instead of edges
• Confusing depth with height
• Starting count from 1 instead of 0

5. In a tree, the level of a node is defined as its depth plus one. Given the tree:

        M
       / \
      N   O
     / \
    P   Q

What is the level of node Q?

hard

A. 1

B. 2

C. 3

D. 4

Solution

1. Step 1: Find depth of node Q

   Path from root M to Q is M -> N -> Q, which has 2 edges, so depth = 2.

2. Step 2: Calculate level using formula

   Level = depth + 1 = 2 + 1 = 3.

3. Final Answer:

   3 -> Option C

4. Quick Check:

   Level = depth + 1 = 3 [OK]

Hint: Level = depth + 1 always [OK]

Common Mistakes:

• Using depth as level directly
• Counting nodes incorrectly
• Confusing level with height