Tree Terminology Root Leaf Height Depth Level in DSA C - Practice Problems & Challenges

Challenge - 5 Problems

❓ Predict Output

intermediate

Output of node depth calculation

What is the output of the depth of node 5 in the given tree after running the code?

DSA C

/* Tree structure:
       1
      / \
     2   3
    /   / \
   4   5   6
*/

#include <stdio.h>

int depth(int node, int parent[], int root) {
    int d = 0;
    while (node != root) {
        node = parent[node];
        d++;
    }
    return d;
}

int main() {
    int parent[7] = {0, 0, 1, 1, 2, 3, 3};
    int root = 1;
    int node = 5;
    printf("%d", depth(node, parent, root));
    return 0;
}

A 1

B 3

C 2

D 0

💡 Hint

Trace the parent array from node 5 up to the root node 1.

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

Node 5's parent is 3, and 3's parent is 1 (the root). So depth = 2.

🧠 Conceptual

intermediate

Identify leaf nodes in a tree

Given the tree below, which nodes are leaf nodes?

DSA C

/* Tree structure:
       10
      /  \
     5    15
    / \     \
   3   7     18
*/

A 10, 3, 7

B 3, 7, 18

C 10, 5, 15

D 5, 15

💡 Hint

Leaf nodes have no children.

Leaf nodes are nodes without children.

Nodes 3, 7, and 18 have no children, so they are leaves.

❓ Predict Output

advanced

Calculate height of a node in a tree

What is the output of the height of node 2 in the tree after running the code?

DSA C

/* Tree structure:
       1
      / \
     2   3
    / \
   4   5
*/

#include <stdio.h>

int max(int a, int b) {
    return (a > b) ? a : b;
}

int height(int node, int left[], int right[]) {
    if (node == 0) return -1;
    return 1 + max(height(left[node], left, right), height(right[node], left, right));
}

int main() {
    int left[6] = {0, 2, 4, 0, 0, 0};
    int right[6] = {0, 3, 5, 0, 0, 0};
    int node = 2;
    printf("%d", height(node, left, right));
    return 0;
}

A 1

B 0

C 3

D 2

💡 Hint

Height is the longest path from the node down to a leaf.

Node 2 has children 4 and 5, both leaves.

Height is 1 + max(height(4), height(5)) = 1 + max(0, 0) = 1.

But since height of leaf is 0, height of node 2 is 1 + 0 = 1.

Wait, code returns -1 for null, so leaf height is 0.

So height of node 2 is 1 + max(0,0) = 1.

🧠 Conceptual

advanced

Determine level of a node in a tree

In the tree below, what is the level of node 7 if the root is at level 0?

DSA C

/* Tree structure:
       1
      / \
     2   3
        / \
       6   7
*/

A 2

B 1

C 3

D 0

💡 Hint

Level is the number of edges from the root to the node.

Root (1) is level 0.

Node 3 is level 1.

Node 7 is child of 3, so level 2.

🔧 Debug

expert

Find the error in height calculation code

What error does the following code produce when calculating the height of a tree?

DSA C

#include <stdio.h>

int height(int node, int left[], int right[]) {
    if (node == 0) return 0;
    return 1 + (height(left[node], left, right) + height(right[node], left, right));
}

int main() {
    int left[6] = {0, 2, 4, 0, 0, 0};
    int right[6] = {0, 3, 5, 0, 0, 0};
    int node = 1;
    printf("%d", height(node, left, right));
    return 0;
}

A It returns 0 for all nodes because base case is incorrect.

B It causes a segmentation fault due to invalid array access.

C It causes infinite recursion and stack overflow.

D It returns the sum of heights of left and right subtrees instead of max, giving wrong height.

💡 Hint

Height should be the longest path, not sum of paths.

The code adds heights of left and right subtrees instead of taking the maximum.

This causes the height to be larger than actual height.

Practice

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

easy

A. The deepest node in the tree

B. The topmost node with no parent

C. A node with exactly two children

D. Any node with no 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: Identify the correct node type

   Nodes with no children are called leaves, not root. The root is unique and at the top.

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 nodes
• Thinking root has children but no parent
• Assuming root is the deepest node

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

easy

A. A node with no children

B. The root node

C. A node with at least one child

D. A node with a parent and children

Solution

1. Step 1: Define a leaf node

   A leaf node is a node that does not have any children nodes connected below it.

2. Step 2: Check options against definition

   Only the option "A node with no children" 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 can have children
• Confusing leaf with root node
• Assuming leaf nodes must have a parent

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 (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. Actually, height is 1.

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:

• Counting nodes instead of edges for height
• Confusing height with depth
• Ignoring that leaves have height 0

4. Given the code snippet below to find the depth of a node in a tree, identify the error:

int depth(Node* root, Node* target) {
    if (root == NULL) return -1;
    if (root == target) return 0;
    int d = depth(root->left, target);
    if (d >= 0) return d + 1;
    d = depth(root->right, target);
    if (d >= 0) return d + 1;
    return -1;
}

medium

A. Function returns -1 when target is root

B. Function does not check both subtrees properly

C. Function correctly calculates depth

D. Function returns depth starting from 1 instead of 0

Solution

1. Step 1: Analyze base cases

   If root is NULL, returns -1 (not found). If root is target, returns 0 (depth zero at root).

2. Step 2: Check recursive calls

   Recursively checks left subtree; if found, adds 1. Else checks right subtree similarly. Returns -1 if not found.

3. Step 3: Confirm correctness

   This correctly calculates depth as number of edges from root to target, starting at 0 for root.

4. Final Answer:

   Function correctly calculates depth -> Option C

5. Quick Check:

   Depth function logic is correct [OK]

Hint: Depth counts edges from root; base case returns 0 [OK]

Common Mistakes:

• Returning wrong base case values
• Not checking both left and right subtrees
• Confusing depth with height

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

        R
       / \
      A   B
     /     \
    C       D
             \
              E

What is the level of node E?

hard

A. 4

B. 3

C. 5

D. 2

Solution

1. Step 1: Find depth of node E

   Depth is number of edges from root R to E. Path: R -> B -> D -> E has 3 edges, so depth = 3.

2. Step 2: Calculate level from depth

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

3. Final Answer:

   4 -> Option A

4. Quick Check:

   Level = depth + 1 = 4 [OK]

Hint: Level = depth + 1, count edges then add one [OK]

Common Mistakes:

• Counting nodes instead of edges for depth
• Forgetting to add 1 for level
• Confusing level with height