Tree Terminology Root Leaf Height Depth Level in DSA C - Interactive Practice

Practice - 5 Tasks

1fill in blank

easy

Complete the code to define the root node of a tree.

DSA C

struct Node* root = [1];

Drag options to blanks, or click blank then click option'

ANULL

B0

Croot

Dnode

Attempts:

3 left

💡 Hint

Common Mistakes

Using 0 instead of NULL

Using an undefined variable like 'root' or 'node'

The root node is the starting point of a tree and is usually initialized to NULL when the tree is empty.

2fill in blank

medium

Complete the code to check if a node is a leaf (has no children).

DSA C

if (node->left == NULL && node->[1] == NULL) {
    // node is a leaf
}

Drag options to blanks, or click blank then click option'

Aparent

Bchild

Croot

Dright

Attempts:

3 left

💡 Hint

Common Mistakes

Checking parent pointer instead of right child

Checking root or child which are not pointers in this context

A leaf node has no left or right children, so both pointers are NULL.

3fill in blank

hard

Fix the error in the function that calculates the height of a tree node.

DSA C

int height(struct Node* node) {
    if (node == NULL) {
        return [1];
    }
    int leftHeight = height(node->left);
    int rightHeight = height(node->right);
    return (leftHeight > rightHeight ? leftHeight : rightHeight) + 1;
}

Drag options to blanks, or click blank then click option'

A1

B0

C-1

DNULL

Attempts:

3 left

💡 Hint

Common Mistakes

Returning 0 instead of -1 for NULL nodes

Returning NULL or 1 which causes wrong height calculation

The height of an empty tree (NULL node) is defined as -1 to make leaf nodes have height 0.

4fill in blank

hard

Fill both blanks to calculate the depth of a node in a tree.

DSA C

int depth(struct Node* node) {
    if (node == NULL) {
        return [1];
    }
    return depth(node->[2]) + 1;
}

Drag options to blanks, or click blank then click option'

A-1

B0

Cparent

Droot

Attempts:

3 left

💡 Hint

Common Mistakes

Using 0 instead of -1 as base case for depth

Using left or right child instead of parent pointer

The depth of NULL (parent of root) is -1 so root depth = depth(NULL) + 1 = 0. Recursively find depth of parent and add 1.

5fill in blank

hard

Fill all three blanks to create a function that returns the level of a node in a tree.

DSA C

int level(struct Node* root, struct Node* node, int currentLevel) {
    if (root == NULL) {
        return [1];
    }
    if (root == node) {
        return [2];
    }
    int downlevel = level(root->left, node, currentLevel [3] 1);
    if (downlevel != -1) {
        return downlevel;
    }
    return level(root->right, node, currentLevel [3] 1);
}

Drag options to blanks, or click blank then click option'

A-1

BcurrentLevel

C+

D-

Attempts:

3 left

💡 Hint

Common Mistakes

Returning 0 instead of -1 when node not found

Returning 1 instead of currentLevel when node found

Using '-' instead of '+' to increase level

If the root is NULL, return -1 meaning node not found. If root is the node, return currentLevel. When searching children, increase currentLevel by 1 using '+'.

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