{"id":683,"date":"2024-10-10T13:39:18","date_gmt":"2024-10-10T08:09:18","guid":{"rendered":"https:\/\/codexplained.in\/?p=683"},"modified":"2025-11-24T15:59:10","modified_gmt":"2025-11-24T10:29:10","slug":"check-if-binary-tree-is-balanced","status":"publish","type":"post","link":"https:\/\/codexplained.in\/?p=683","title":{"rendered":"Check if Binary Tree is Balanced"},"content":{"rendered":"
\n#include <stdio.h>\n#include <stdlib.h>\n\n\/\/ Definition for a binary tree node.\nstruct Node {\n    int data;\n    struct Node* left;\n    struct Node* right;\n};\n\n\/\/ Function to create a new node.\nstruct Node* createNode(int data) {\n    struct Node* newNode = (struct Node*)malloc(sizeof(struct Node));\n    newNode->data = data;\n    newNode->left = NULL;\n    newNode->right = NULL;\n    return newNode;\n}\n\n\/\/ Function to find the height of a tree.\n\/\/ Returns -1 if the tree is unbalanced.\nint height(struct Node* root) {\n    \/\/ An empty tree has a height of 0.\n    if (root == NULL)\n        return 0;\n\n    \/\/ Get the height of the left and right subtrees.\n    int leftHeight = height(root->left);\n    int rightHeight = height(root->right);\n\n    \/\/ If left or right subtree is unbalanced, return -1.\n    if (leftHeight == -1 || rightHeight == -1)\n        return -1;\n\n    \/\/ If the difference in height between left and right subtrees is more than 1, return -1.\n    if (abs(leftHeight - rightHeight) > 1)\n        return -1;\n\n    \/\/ Otherwise, return the height of the tree.\n    return 1 + (leftHeight > rightHeight ? leftHeight : rightHeight);\n}\n\n\/\/ Function to check if the tree is balanced.\nint isBalanced(struct Node* root) {\n    return height(root) != -1;\n}\n\n\/\/ Main function to test the above functions.\nint main() {\n    struct Node* root = createNode(1);\n    root->left = createNode(2);\n    root->right = createNode(3);\n    root->left->left = createNode(4);\n    root->left->right = createNode(5);\n    root->left->left->left = createNode(8);\n\n    if (isBalanced(root))\n        printf("The binary tree is balanced.\\n");\n    else\n        printf("The binary tree is not balanced.\\n");\n\n    return 0;\n}\n\n<\/pre><\/div>\n\n\n
Explanation of the Code:<\/h3>\n\n\n\n
    \n
  1. Node Structure<\/strong>:\n
      \n
    • struct Node<\/code> represents a node of the binary tree, containing:\n
        \n
      • data<\/code>: Value stored in the node.<\/li>\n\n\n\n
      • left<\/code>: Pointer to the left child.<\/li>\n\n\n\n
      • right<\/code>: Pointer to the right child.<\/li>\n<\/ul>\n<\/li>\n<\/ul>\n<\/li>\n\n\n\n
      • Create Node<\/strong>:\n
          \n
        • createNode(int data)<\/code> allocates memory for a new node and initializes it with the given value, setting its left and right pointers to NULL<\/code>.<\/li>\n<\/ul>\n<\/li>\n\n\n\n
        • Height Calculation<\/strong>:\n
            \n
          • height(struct Node* root)<\/code> calculates the height of a subtree rooted at root<\/code>.<\/li>\n\n\n\n
          • It recursively finds the heights of the left and right subtrees.<\/li>\n\n\n\n
          • If any subtree is unbalanced or the height difference exceeds 1, it returns -1<\/code>.<\/li>\n\n\n\n
          • Otherwise, it returns the height of the current subtree.<\/li>\n<\/ul>\n<\/li>\n\n\n\n
          • Check for Balanced Tree<\/strong>:\n
              \n
            • isBalanced(struct Node* root)<\/code> checks if the binary tree is balanced by calling height()<\/code>.<\/li>\n\n\n\n
            • If the height function returns -1<\/code>, it means the tree is unbalanced; otherwise, it is balanced.<\/li>\n<\/ul>\n<\/li>\n\n\n\n
            • Main Function<\/strong>:\n
                \n
              • Constructs a sample tree and checks if it is balanced.<\/li>\n\n\n\n
              • The output is printed based on whether the tree is balanced.<\/li>\n<\/ul>\n<\/li>\n<\/ol>\n\n\n\n
                Output:<\/h3>\n\n\n\n
                For the given sample tree:<\/p>\n\n\n\n
                       1\n      \/ \\\n     2   3\n    \/ \\\n   4   5\n  \/\n 8\n<\/code><\/pre>\n\n\n\n
                The output would be:<\/p>\n\n\n\n
                The binary tree is not balanced.\n<\/code><\/pre>\n\n\n\n
                Explanation of Output<\/strong>:<\/p>\n\n\n\n
                  \n
                • In this case, the left subtree of 2<\/code> (which includes 4<\/code> and 8<\/code>) is deeper than its right subtree.<\/li>\n\n\n\n
                • The height difference between the left and right subtrees of 2<\/code> is more than 1.<\/li>\n\n\n\n
                • Therefore, the tree is identified as unbalanced.<\/li>\n<\/ul>\n\n\n\n
                  <\/p>\n