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

Challenge - 5 Problems

🧠 Conceptual

intermediate

Identify the root node in a tree

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

A The node with the lowest height

B The node with no parent

C The node with no children

D The node with the highest depth

💡 Hint

Think about the starting point of the tree.

The root node is the topmost node in a tree and has no parent node.

❓ Predict Output

intermediate

Find the leaf nodes in a tree

Given the following tree nodes and their children, which nodes are leaves?

DSA C++

Node 1: children = [2, 3]
Node 2: children = [4]
Node 3: children = []
Node 4: children = []

A [1, 2]

B [1, 4]

C [2, 3]

D [3, 4]

💡 Hint

Leaves have no children.

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

❓ Predict Output

advanced

Calculate the height of a node

What is the height of node 2 in the following tree? Structure: 1 ├─ 2 │ └─ 4 └─ 3

DSA C++

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

A 0

B 2

C 1

D 3

💡 Hint

Count edges from node 2 down to its farthest leaf.

Node 2 has one child (4), which is a leaf. So height is 1 edge.

❓ Predict Output

advanced

Determine the depth of a node

What is the depth of node 4 in the tree below? Structure: 1 ├─ 2 │ └─ 4 └─ 3

DSA C++

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

A 2

B 1

C 0

D 3

💡 Hint

Count edges from root (1) to node 4.

Path from root to node 4 is 1 -> 2 -> 4, which has 2 edges.

🧠 Conceptual

expert

Identify the level of a node in a tree

In a tree, what does the level of a node represent?

A The number of edges from the root plus one

B The number of children the node has

C The height of the node

D The number of leaf nodes in the subtree

💡 Hint

Level is closely related to depth but starts counting from 1.

Level is depth plus one, counting the root as level 1.

Practice

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

easy

A. A node with exactly two children

B. A node with no children

C. The topmost node with no parent

D. Any node at the bottom level

Solution

1. Step 1: Understand the root node concept

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

2. Step 2: Differentiate root from other nodes

   Leaf nodes have no children, but root has no parent. Bottom level nodes are leaves or internal nodes, not necessarily root.

3. Final Answer:

   The topmost node with no parent -> Option C

4. Quick Check:

   Root = topmost node with no parent [OK]

Hint: Root is the only node without a parent [OK]

Common Mistakes:

• Confusing root with leaf node
• Thinking root must have children
• Assuming root is at bottom level

2. Which of the following is the correct way to declare a simple binary tree node struct in C++?

easy

A. struct Node { int data; Node* left; Node* right; };

B. struct Node { int data; Node left; Node right; };

C. struct Node { int data; Node* left; int right; };

D. struct Node { int data; int left; int right; };

Solution

1. Step 1: Check pointer usage for child nodes

   Child nodes must be pointers to Node to allow recursive structure.

2. Step 2: Validate data types of members

   Data is int, left and right are pointers to Node, so struct Node { int data; Node* left; Node* right; }; is correct.

3. Final Answer:

   struct Node { int data; Node* left; Node* right; }; -> Option A

4. Quick Check:

   Child nodes use pointers in struct [OK]

Hint: Child nodes must be pointers to Node type [OK]

Common Mistakes:

• Using Node instead of Node* for children
• Mixing int and Node types for children
• Missing semicolon at struct end

3. Consider the following tree:

        10
       /  \
      5    15
     /    /  \
    3    12  20

What is the height of the node with value 5?

medium

A. 1

B. 2

C. 3

D. 0

Solution

1. Step 1: Understand height definition

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

2. Step 2: Calculate height of node 5

   Node 5 has left child 3 (leaf). Longest path from 5 to leaf is 5 -> 3, which is 1 edge. Height of 3 is 0. Height of 5 = 1 + max height of children = 1 + 0 = 1. However, node 5 has no right child, so max height is 1. So height is 1. But the question asks for height of node 5. Since 3 is leaf (height 0), height of 5 is 1. But 2 says 2, which is incorrect. So correct answer is 1 (1).

3. Final Answer:

   1 -> Option A

4. Quick Check:

   Height = edges to deepest leaf = 1 [OK]

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

Common Mistakes:

• Counting nodes instead of edges
• Confusing height with depth
• Ignoring missing right child

4. Given the following code snippet, what is the error?

struct Node {
  int data;
  Node* left;
  Node* right;
};

Node* root = new Node{10, nullptr, nullptr};
root->left = new Node{5, nullptr, nullptr};
root->left->left = new Node{3, nullptr, nullptr};
root->right = new Node{15, nullptr, nullptr};
root->right->right = new Node{20, nullptr, nullptr};
root->right->left = 12;

medium

A. Incorrect initialization of root node

B. Missing semicolon after struct definition

C. Using nullptr instead of NULL

D. Assigning int 12 to a Node* pointer

Solution

1. Step 1: Analyze the last assignment

   Line root->right->left = 12; assigns integer 12 to a pointer Node* left, which is invalid.

2. Step 2: Check pointer assignment rules

   Pointers must be assigned addresses or nullptr, not raw integers.

3. Final Answer:

   Assigning int 12 to a Node* pointer -> Option D

4. Quick Check:

   Pointer must hold address, not int [OK]

Hint: Pointers cannot hold raw integers [OK]

Common Mistakes:

• Ignoring type mismatch in assignment
• Thinking nullptr and NULL difference causes error
• Overlooking semicolon presence

5. In a tree, the depth of a node is defined as the number of edges from the root to that node. Given the tree:

        1
       / \
      2   3
     /   / \
    4   5   6
       /
      7

What is the depth of node 7 and what is its level?

hard

A. Depth = 3, Level = 3

B. Depth = 3, Level = 4

C. Depth = 4, Level = 3

D. Depth = 4, Level = 4

Solution

1. Step 1: Calculate depth of node 7

   Path from root (1) to 7 is 1 -> 3 -> 5 -> 7, which has 3 edges, so depth = 3.

2. Step 2: Calculate level of node 7

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

3. Final Answer:

   Depth = 3, Level = 4 -> Option B

4. Quick Check:

   Level = depth + 1 = 4 [OK]

Hint: Level = depth + 1 always [OK]

Common Mistakes:

• Confusing depth with level
• Counting nodes instead of edges for depth
• Starting depth count from 0 or 1 incorrectly