Check if Binary Tree is Balanced in DSA C++ - Build from Scratch

Check if Binary Tree is Balanced

📖 Scenario: Imagine you are building a program to check if a family tree is well balanced. A balanced tree means no branch is too long compared to others, making it easier to find family members quickly.

🎯 Goal: You will create a binary tree, add a helper variable, write a function to check if the tree is balanced, and finally print the result.

📋 What You'll Learn

Create a binary tree with the exact nodes and structure given

Add a helper function to calculate height

Write a function called isBalanced that returns true if the tree is balanced

Print "Balanced" if the tree is balanced, otherwise print "Not Balanced"

💡 Why This Matters

🌍 Real World

Balanced trees are used in databases and file systems to keep data organized for fast searching and updating.

💼 Career

Understanding tree balance helps in roles like software development, data engineering, and system design where efficient data structures are crucial.

1

Create the Binary Tree Structure

Create a struct called Node with an int data, and two pointers left and right. Then create the exact binary tree below by creating Node pointers: root with value 1, root's left child 2, root's right child 3, left child of 2 is 4, right child of 2 is 5.

DSA C++

// Define struct Node
// Create nodes and link them to form the tree
// Your code here

Hint

Define the Node struct first. Then create nodes with new Node(value) and link them using ->left and ->right.

2

Add a Helper Function to Calculate Height

Add a function called height that takes a Node* called root and returns an int. It should return 0 if root is nullptr. Otherwise, return 1 plus the maximum height of the left and right subtrees.

DSA C++

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

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);

// Add height function below
// Your code here

Hint

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

3

Write the isBalanced Function

Write a function called isBalanced that takes a Node* called root and returns a bool. It should return true if the tree is balanced. A tree is balanced if for every node, the difference between the height of left and right subtrees is at most 1, and both left and right subtrees are balanced.

DSA C++

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

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);

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

// Write isBalanced function below
// Your code here

Hint

Check height difference at current node and recursively check left and right subtrees.

4

Print if the Tree is Balanced

Write a main function that calls isBalanced(root). If it returns true, print "Balanced". Otherwise, print "Not Balanced".

DSA C++

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

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);

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

bool isBalanced(Node* root) {
    if (root == nullptr) return true;
    int leftHeight = height(root->left);
    int rightHeight = height(root->right);
    if (abs(leftHeight - rightHeight) > 1) return false;
    return isBalanced(root->left) && isBalanced(root->right);
}

int main() {
    // Print "Balanced" or "Not Balanced" based on isBalanced(root)
    // Your code here
}

Hint

Use cout to print the result based on isBalanced(root).