Tree Terminology Root Leaf Height Depth Level in DSA Python - Cheat Sheet & Quick Revision

Recall & Review

beginner

What is the root of a tree?

The root is the topmost node of a tree. It has no parent and is the starting point of the tree.

beginner

Define a leaf node in a tree.

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

intermediate

What does the height of a node represent in a tree?

The height of a node is the number of edges on the longest path from that node down to a leaf.

intermediate

Explain the depth of a node in a tree.

The depth of a node is the number of edges from the root node down to that node.

beginner

What is the level of a node in a tree?

The level of a node is its depth plus one. The root is at level 1, its children at level 2, and so on.

Which node in a tree has no parent?

A Sibling

B Root

C Child

D Leaf

The root node is the only node without a parent.

What do we call a node with no children?

A Root

B Internal node

C Leaf

D Parent

A leaf node has no children.

The height of a node is the number of edges on the longest path from the node to a:

A Leaf

B Sibling

C Root

D Parent

Height counts edges down to the farthest leaf.

Depth of a node is measured by counting edges from:

A Root to node

B Leaf to node

C Node to sibling

D Node to parent

Depth is edges from root down to the node.

If a node is at depth 3, what is its level?

A 5

B 3

C 2

D 4

Level = depth + 1, so 3 + 1 = 4.

Describe the difference between the root, leaf, and internal nodes in a tree.

Think about where each node sits in the tree structure.

Explain how height, depth, and level relate to each other in a tree.

Consider paths from root and to leaves.

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