Why Tree Terminology Root Leaf Height Depth Level in DSA C++?

The Big Idea

Discover how simple words can unlock the power to organize and explore complex data like family trees or computer files!

The Scenario

Imagine you have a family tree drawn on paper. You want to find out who is the oldest ancestor, who has no children, and how far each person is from the oldest ancestor. Doing this by just looking and guessing can be confusing and slow.

The Problem

Manually checking each person's position in the tree is error-prone and takes a lot of time. You might forget who is at the top (root), who has no children (leaf), or how deep someone is in the tree. This makes understanding and using the tree very hard.

The Solution

Using clear tree terms like root, leaf, height, depth, and level helps us describe and work with trees easily. These terms give us a simple way to talk about positions and distances in the tree, making it easier to write code that handles trees correctly.

Before vs After

✗ Before

// Manually checking nodes
if (node.parent == nullptr) {
  // root node
}
if (node.children.empty()) {
  // leaf node
}

✓ After

int depth(Node* node) {
  if (node == nullptr) return -1;
  return 1 + depth(node->parent);
}

What It Enables

It enables us to build and navigate complex tree structures easily and correctly in programs.

Real Life Example

File systems on your computer use trees. The root is the main folder, leaves are files with no subfolders, and height shows how deep folders are nested.

Key Takeaways

Root is the top node with no parent.

Leaf nodes have no children.

Height, depth, and level help measure positions in the tree.

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