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

The Big Idea

Discover how simple words like root and leaf unlock the secrets of complex trees!

The Scenario

Imagine you have a family tree drawn on paper with many names and connections. You want to find how far a person is from the oldest ancestor or who has no children. Doing this by looking at the paper every time is confusing and slow.

The Problem

Manually tracing connections on paper or in a list is slow and easy to mess up. You might forget who is connected to whom or how deep someone is in the tree. This causes mistakes and wastes time.

The Solution

Using tree terminology like root, leaf, height, depth, and level helps us talk about and work with trees clearly. It makes it easy to find important parts and understand the tree's shape without confusion.

Before vs After

✗ Before

/* Manually checking if node is leaf */
if (node->left == NULL && node->right == NULL) {
    // leaf node
}

✓ After

int isLeaf(Node* node) {
    return node->left == NULL && node->right == NULL;
}

What It Enables

It lets us write clear code to explore and use trees efficiently, like finding the oldest ancestor or the deepest leaf quickly.

Real Life Example

Family trees, company hierarchies, or folder structures on your computer all use these terms to organize and find information fast.

Key Takeaways

Root is the starting point of the tree.

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. 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