Height of Binary Tree in DSA C - Build from Scratch

Height of Binary Tree

📖 Scenario: You are working on a program that manages a family tree. Each person can have children, and you want to find out how many generations are in the family tree. This means finding the height of the tree, which is the longest path from the oldest ancestor to the youngest descendant.

🎯 Goal: Build a program in C that creates a simple binary tree, then calculates and prints its height.

📋 What You'll Learn

Create a binary tree node structure with integer data and left and right child pointers

Manually create a binary tree with 5 nodes in a specific shape

Write a recursive function to calculate the height of the binary tree

Print the height of the binary tree

💡 Why This Matters

🌍 Real World

Binary trees are used in many applications like organizing family trees, file systems, and decision processes.

💼 Career

Understanding tree structures and recursion is important for software development, especially in areas like databases, compilers, and AI.

1

Create the binary tree node structure and build the tree

Write the struct Node with int data, struct Node* left, and struct Node* right. Then create 5 nodes named root, node1, node2, node3, and node4. Assign data values 1, 2, 3, 4, and 5 respectively. Connect them to form this tree:

1
/ \
2 3
/ \
4 5

DSA C

#include 
#include 

// Define struct Node and create nodes root, node1, node2, node3, node4
// Assign data and connect nodes as shown
// Your code here

Hint

Start by defining the Node structure. Then create variables for each node and assign their data and child pointers to build the tree shape.

2

Create a function to calculate the height of the tree

Write a recursive function called height that takes a pointer to Node named root and returns an int. The function should return 0 if root is NULL. Otherwise, it should return 1 plus the maximum height of the left and right subtrees.

DSA C

#include 
#include 

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

int main() {
    Node root, node1, node2, node3, node4;

    root.data = 1;
    node1.data = 2;
    node2.data = 3;
    node3.data = 4;
    node4.data = 5;

    root.left = &node1;
    root.right = &node2;
    node1.left = &node3;
    node1.right = &node4;
    node2.left = NULL;
    node2.right = NULL;
    node3.left = NULL;
    node3.right = NULL;
    node4.left = NULL;
    node4.right = NULL;

    return 0;
}

// Write the recursive function height here
// Your code here

Hint

Use recursion to find the height of left and right children, then return the bigger one plus one.

3

Call the height function in main

Inside main, create an int variable called tree_height. Assign it the result of calling height with the address of root.

DSA C

#include 
#include 

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

int height(Node* root) {
    if (root == NULL) {
        return 0;
    }
    int left_height = height(root->left);
    int right_height = height(root->right);
    return (left_height > right_height ? left_height : right_height) + 1;
}

int main() {
    Node root, node1, node2, node3, node4;

    root.data = 1;
    node1.data = 2;
    node2.data = 3;
    node3.data = 4;
    node4.data = 5;

    root.left = &node1;
    root.right = &node2;
    node1.left = &node3;
    node1.right = &node4;
    node2.left = NULL;
    node2.right = NULL;
    node3.left = NULL;
    node3.right = NULL;
    node4.left = NULL;
    node4.right = NULL;

    // Create int tree_height and assign height(&root)
    // Your code here

    return 0;
}

Hint

Call the height function with &root and store the result in tree_height.

4

Print the height of the binary tree

Add a printf statement in main to print the text "Height of the tree: " followed by the value of tree_height and a newline.

DSA C

#include 
#include 

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

int height(Node* root) {
    if (root == NULL) {
        return 0;
    }
    int left_height = height(root->left);
    int right_height = height(root->right);
    return (left_height > right_height ? left_height : right_height) + 1;
}

int main() {
    Node root, node1, node2, node3, node4;

    root.data = 1;
    node1.data = 2;
    node2.data = 3;
    node3.data = 4;
    node4.data = 5;

    root.left = &node1;
    root.right = &node2;
    node1.left = &node3;
    node1.right = &node4;
    node2.left = NULL;
    node2.right = NULL;
    node3.left = NULL;
    node3.right = NULL;
    node4.left = NULL;
    node4.right = NULL;

    int tree_height = height(&root);

    // Print the height of the tree
    // Your code here

    return 0;
}

Hint

Use printf("Height of the tree: %d\n", tree_height); to show the height.

Practice

1. What is the height of a binary tree with only one node (the root)?

easy

A. 0

B. 1

C. 2

D. Undefined

Solution

1. Step 1: Understand height definition

   The height of a binary tree is the number of edges on the longest path from the root to a leaf.

2. Step 2: Apply to single node tree

   With only one node (root), the longest path has length 0 edges.

3. Final Answer:

   0 -> Option A

4. Quick Check:

   Height of single node tree = 0 [OK]

Hint: Height counts edges on longest root-to-leaf path [OK]

Common Mistakes:

• Thinking height is 1 for single node
• Confusing height with number of nodes
• Assuming height is undefined for single node

2. Which of the following is the correct C function signature to calculate the height of a binary tree node?

easy

A. void height(struct Node root);

B. int height(Node root);

C. int height(struct Node* root);

D. int height(struct Node root);

Solution

1. Step 1: Check parameter type for tree node

   In C, a tree node is usually passed as a pointer to struct Node.

2. Step 2: Check return type and parameter correctness

   The function returns an int (height) and takes a pointer to struct Node.

3. Final Answer:

   int height(struct Node* root); -> Option C

4. Quick Check:

   Correct signature uses pointer to struct Node [OK]

Hint: Use pointer to struct Node for tree parameters [OK]

Common Mistakes:

• Passing struct Node by value instead of pointer
• Using void return type instead of int
• Missing struct keyword in parameter

3. What is the output of the following code snippet calculating the height of this binary tree?

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

int height(struct Node* root) {
  if (root == NULL) return 0;
  int leftHeight = height(root->left);
  int rightHeight = height(root->right);
  return (leftHeight > rightHeight ? leftHeight : rightHeight) + 1;
}

// Tree:
//     10
//    /  \
//   5    15
//        /
//       12

int main() {
  struct Node n12 = {12, NULL, NULL};
  struct Node n15 = {15, &n12, NULL};
  struct Node n5 = {5, NULL, NULL};
  struct Node n10 = {10, &n5, &n15};
  printf("%d", height(&n10));
  return 0;
}

medium

A. 1

B. 2

C. 4

D. 3

Solution

1. Step 1: Trace left subtree height

   Left subtree of root (10) has node 5 only, height = 1.

2. Step 2: Trace right subtree height

   Right subtree has nodes 15 and 12. Height is 2 (15 -> 12).

3. Step 3: Calculate total height

   Height = max(1, 2) + 1 (for root) = 3.

4. Final Answer:

   3 -> Option D

5. Quick Check:

   Height = 3 [OK]

Hint: Height = max(left, right) + 1 recursively [OK]

Common Mistakes:

• Counting edges instead of nodes
• Ignoring one subtree height
• Off-by-one error in return statement

4. Identify the error in this height function and select the correct fix:

int height(struct Node* root) {
  if (root == NULL) return -1;
  int leftHeight = height(root->left);
  int rightHeight = height(root->right);
  return (leftHeight > rightHeight ? leftHeight : rightHeight) + 1;
}

medium

A. Change base case return from -1 to 1

B. Change base case return from -1 to 0

C. Remove +1 from return statement

D. Change recursive calls to root->right and root->left swapped

Solution

1. Step 1: Understand base case meaning

   Base case returns height for empty tree. Returning -1 means height counts edges, not nodes.

2. Step 2: Fix base case for node count height

   To count nodes, base case should return 0 for NULL.

3. Final Answer:

   Change base case return from -1 to 0 -> Option B

4. Quick Check:

   Base case 0 for NULL node height [OK]

Hint: Base case for NULL should return 0 for node height [OK]

Common Mistakes:

• Returning -1 causes off-by-one height
• Removing +1 leads to wrong height
• Swapping left and right recursive calls unnecessary

5. Given a binary tree where each node has either 0 or 2 children, what is the height of a full binary tree with 7 nodes? Select the correct height.

hard

A. 3

B. 4

C. 2

D. 5

Solution

1. Step 1: Understand full binary tree properties

   A full binary tree with all nodes having 0 or 2 children has nodes count = 2^h - 1, where h is height.

2. Step 2: Calculate height from nodes count

   Given nodes = 7, solve 2^h - 1 = 7 -> 2^h = 8 -> h = 3.

3. Final Answer:

   3 -> Option A

4. Quick Check:

   Full binary tree height for 7 nodes = 3 [OK]

Hint: Full tree nodes = 2^height - 1 formula [OK]

Common Mistakes:

• Confusing height with number of edges
• Using incomplete binary tree formula
• Miscounting nodes or height