Tree Terminology Root Leaf Height Depth Level in DSA C++ - 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?

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.

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?

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 Leaf

C Internal node

D Root

The root node is the only node without a parent.

A node with no children is called a?

A Root

B Leaf

C Parent

D Ancestor

Leaf nodes have no children and are at the ends of branches.

What does the height of a tree measure?

A Edges from node to leaf

B Edges from root to node

C Number of nodes

D Number of leaves

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

Depth of a node is the number of edges from?

A Node to leaf

B Sibling to node

C Root to node

D Leaf to root

Depth counts edges from the root down to the node.

If the root is at level 1, what level are its children at?

A 2

B 1

C 0

D 3

Children of root are at level 2 (depth 1 + 1).

Describe the difference between depth and height of a node in a tree.

Think about where you start counting edges for each.

Explain what a leaf node is and how it differs from the root node.

Consider the position and connections of each node.

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