Tree Terminology Root Leaf Height Depth Level in DSA C - Build from Scratch

Understanding Tree Terminology: Root, Leaf, Height, Depth, Level

📖 Scenario: Imagine you are organizing a family tree. Each person is a node, and relationships form a tree structure. You want to understand key terms like root, leaf, height, depth, and level to describe this tree clearly.

🎯 Goal: You will build a simple tree structure in C and write code to identify the root node, leaf nodes, calculate the height of the tree, find the depth of a specific node, and print the level of each node.

📋 What You'll Learn

Create a simple tree with exactly 5 nodes with given connections

Identify the root node

Identify leaf nodes

Calculate the height of the tree

Calculate the depth of a given node

Print the level of each node

💡 Why This Matters

🌍 Real World

Understanding tree terminology helps in organizing hierarchical data like family trees, file systems, and organizational charts.

💼 Career

Tree structures are fundamental in software engineering, used in databases, search algorithms, and UI components.

1

Create the Tree Structure with 5 Nodes

Create a struct called Node with an integer data, and two pointers left and right. Then create 5 nodes named node1 to node5 with data values 1 to 5 respectively. Connect them to form this tree:

1
/ \
2 3
/ \
4 5

DSA C

# Define struct Node and create 5 nodes with data 1 to 5
# Connect nodes to form the tree

Hint

Start by defining the Node struct with data, left, and right. Then create each node with the given data and connect them as shown.

2

Identify the Root and Leaf Nodes

Create a pointer root and set it to point to node1. Then create a function isLeaf that takes a Node* and returns 1 if both left and right are NULL, else returns 0.

DSA C

# Create pointer root to node1
// Define isLeaf function

Hint

Set root to point to node1. The isLeaf function checks if both children are NULL.

3

Calculate the Height of the Tree

Write a recursive function height that takes a Node* and returns the height of the tree. Height is 0 if node is NULL. Otherwise, height is 1 plus the maximum height of left and right subtrees.

DSA C

# Write recursive function height

Hint

Use recursion to find the height of left and right subtrees, then return 1 plus the larger one.

4

Calculate Depth and Print Levels of Nodes

Write a function depth that takes Node* root, Node* target, and int currentDepth, and returns the depth of target node from root. Return -1 if not found. Then in main, print the height of the tree, the depth of node5, and print the level (depth + 1) of each node from node1 to node5.

DSA C

# Write depth function
# Print height, depth of node5, and levels of nodes 1 to 5

Hint

The depth function searches for the target node and returns its depth from root. Level is depth + 1. Use printf to show results.

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