Height and depth of trees in Data Structures Theory - Cheat Sheet & Quick Revision

Recall & Review

beginner

What is the depth of a node in a tree?

The depth of a node is the number of edges from the tree's root node to that node. It tells how far the node is from the root.

beginner

Define the height of a tree.

The height of a tree is the length of the longest path from the root node down to the farthest leaf node. It shows how tall the tree is.

intermediate

How is the height of a node different from the depth of a node?

The depth measures distance from the root to the node, while the height measures the longest distance from the node down to a leaf.

beginner

If the root node has depth 0, what is the depth of its immediate children?

The immediate children of the root node have a depth of 1 because they are one edge away from the root.

intermediate

Why is understanding height and depth important in trees?

Knowing height and depth helps us understand tree structure, optimize searches, and analyze algorithms like traversals and balancing.

What is the depth of the root node in a tree?

A 1

B Height of the tree

C Depends on the tree

D 0

The root node is at depth 0 because it has no edges above it.

The height of a leaf node is always:

A 0

B 1

C Equal to the tree height

D Depends on the depth

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

If a node has depth 3, how many edges are there from the root to this node?

A 1

B 2

C 3

D 4

Depth counts the number of edges from root to the node, so depth 3 means 3 edges.

Which of the following best describes the height of a tree?

A Number of nodes in the tree

B Longest path from root to any leaf

C Number of children of the root

D Depth of the root node

Height is the length of the longest path from the root to a leaf.

If a tree has height 5, what is the minimum possible depth of a leaf node?

A 1

B 5

C 0

D Cannot be determined

The minimum depth of a leaf node is at least 1 because the root is at depth 0 and leaves are below it.

Explain in your own words the difference between the height and depth of nodes in a tree.

Think about how far a node is from the top versus how far it is from the bottom.

Why is it useful to know the height and depth when working with trees in computer science?

Consider how these measures affect how we navigate or organize data.

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