Height of Binary Tree in DSA C++ - Build from Scratch

Height of Binary Tree

📖 Scenario: You are working with a simple family tree where each person can have up to two children. You want to find out how tall this family tree is, meaning how many generations it has from the oldest ancestor down to the youngest descendant.

🎯 Goal: Build a program that creates a binary tree representing the family tree, then calculates and prints the height of this tree.

📋 What You'll Learn

Create a binary tree with exactly 5 nodes with given values

Add a helper variable to store the root of the tree

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 real-world applications like organizing family trees, file systems, and decision-making processes.

💼 Career

Understanding binary trees and recursion is essential for software engineering roles involving data structures, algorithms, and system design.

1

Create the Binary Tree Nodes

Create a binary tree with nodes having these exact integer values: 1 as root, 2 as left child of root, 3 as right child of root, 4 as left child of node 2, and 5 as right child of node 2. Use the struct Node with int data, Node* left, and Node* right. Initialize all pointers to nullptr.

DSA C++

#include 
using namespace std;

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

    Node(int val) : data(val), left(nullptr), right(nullptr) {}
};

int main() {
    // Create nodes with values 1, 2, 3, 4, 5 and link them as described
    // Your code here
}

Hint

Start by creating the root node with value 1. Then create nodes 2 and 3 as children of root. Finally, add nodes 4 and 5 as children of node 2.

2

Add Root Pointer Variable

Add a pointer variable called root that points to the root node of the binary tree you created in Step 1.

DSA C++

#include 
using namespace std;

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

    Node(int val) : data(val), left(nullptr), right(nullptr) {}
};

int main() {
    Node* root = new Node(1);
    root->left = new Node(2);
    root->right = new Node(3);
    root->left->left = new Node(4);
    root->left->right = new Node(5);
    // root pointer already declared above
    // Your code here
}

Hint

You already declared root in Step 1. Just make sure it is named exactly root.

3

Write Recursive Function to Calculate Height

Write a recursive function called height that takes a Node* parameter called node and returns an int representing the height of the binary tree rooted at node. The height is 0 if node is nullptr. Otherwise, it is 1 plus the maximum height of the left and right subtrees.

DSA C++

#include 
using namespace std;

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

    Node(int val) : data(val), left(nullptr), right(nullptr) {}
};

int height(Node* node) {
    // Return 0 if node is nullptr
    // Otherwise return 1 + max height of left and right
    // Your code here
}

int main() {
    Node* root = new Node(1);
    root->left = new Node(2);
    root->right = new Node(3);
    root->left->left = new Node(4);
    root->left->right = new Node(5);
}

Hint

Use a base case to return 0 if node is nullptr. Then recursively call height on left and right children. Return 1 plus the larger of the two heights.

4

Print the Height of the Binary Tree

Use cout to print the height of the binary tree by calling height(root). The output should be exactly the integer height value.

DSA C++

#include 
using namespace std;

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

    Node(int val) : data(val), left(nullptr), right(nullptr) {}
};

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

int main() {
    Node* root = new Node(1);
    root->left = new Node(2);
    root->right = new Node(3);
    root->left->left = new Node(4);
    root->left->right = new Node(5);
    // Print the height of the tree
    cout << height(root) << endl;
}

Hint

Call height(root) and print the result using cout. The height of this tree is 3.