Balanced Binary Tree

Difficulty Level Easy
Frequently asked in Amazon Bloomberg Google Microsoft
Binary Tree Depth First Search Recursion TreeViews 2333

In the balanced binary tree problem, we have given the root of a binary tree. We have to determine whether or not it is height balance.

Examples

Input

Balanced Binary Tree

Output

true

Input

Balanced Binary Tree

Output:

false

Balanced Binary Tree

Every node in a balanced binary tree has a difference of 1 or less between its left and right subtree height. An empty tree always follows height balance.
That is, for a balanced binary tree,
-1 <= Height of left subtree – Height of right subtree <= 1

Naive Approach for Balanced Binary Tree

For every node to calculate the height of its left and right subtree, if the difference is greater than 1, return false, else recur for its left and right subtree and return true if both are balanced, in all other cases return false.
Base Case: Empty tree follows height balance.

  1. Start from the root. If the root is null, return true.
  2. Calculate the height of its left and right subtree and store them in variables named leftHeight and rightHeight respectively.
  3. Recursively call the balance height function for root’s left and right subtree. If both left and right subtree are balanced and the difference between the leftHeight and rightHeight is less than or equals to 1, return true, else return false.

Time Complexity = O(n^2)

JAVA Code

public class BalancedBinaryTree {
    static class Node {
        int data;
        Node left;
        Node right;

        public Node(int data) {
            this.data = data;
            left = right = null;
        }
    }

    // Function to calculate height of a tree rooted at root
    private static int height(Node root) {
        if (root == null) {
            // Height of empty tree is 0
            return 0;
        }
        // Height of tree is 1 + maximum of height of left or right subtree
        return 1 + Math.max(height(root.left), height(root.right));
    }

    // Function to check if given tree is balanced or not
    private static boolean isBalanced(Node root) {
        if (root == null) {
            // Empty tree is always balanced
            return true;
        }

        // Find the left subtree height and right subtree height
        int leftHeight = height(root.left);
        int rightHeight = height(root.right);

        // If this node is balanced and also its left and right subtree are balanced return true
        // else return false
        return (Math.abs(leftHeight - rightHeight) <= 1) && isBalanced(root.left)
                && isBalanced(root.right);
    }

    public static void main(String[] args) {
        // Tree in example 1
        Node root = new Node(18);
        root.left = new Node(4);
        root.right = new Node(20);
        root.right.left = new Node(13);
        root.right.right = new Node(70);

        System.out.println(isBalanced(root));

        // Tree in example 2
        Node root2 = new Node(3);
        root2.left = new Node(4);
        root2.right = new Node(8);
        root2.left.left = new Node(5);
        root2.left.right = new Node(9);
        root2.right.right = new Node(7);
        root2.right.right.left = new Node(6);

        System.out.println(isBalanced(root2));
    }
}

C++ Code

#include <iostream>
using namespace std;

class Node {
    public:
    int data;
    Node *left;
    Node *right;
};

// Function to calculate height of a tree rooted at root
int height(Node *root) {
    if (root == NULL) {
        // Height of empty tree is 0
        return 0;
    }
    // Height of tree is 1 + maximum of height of left or right subtree
    return 1 + std::max(height(root->left), height(root->right));
}

// Function to check if given tree is balanced or not
bool isBalanced(Node *root) {
    if (root == NULL) {
        // Empty tree is always balanced
        return true;
    }

    // Find the left subtree height and right subtree height
    int leftHeight = height(root->left);
    int rightHeight = height(root->right);

    // If this node is balanced and also its left and right subtree are alanced return true
    // else return false
    return (abs(leftHeight - rightHeight) <= 1) && isBalanced(root->left)
            && isBalanced(root->right);
}

// Function to allocate new memory to a tree node
Node* newNode(int data) { 
    Node *node = new Node(); 
    node->data = data; 
    node->left = NULL; 
    node->right = NULL;
  
    return (node); 
}

int main() {
  // Tree in example 1
    Node *root = newNode(18);
    root->left = newNode(4);
    root->right = newNode(20);
    root->right->left = newNode(13);
    root->right->right = newNode(70);

    if (isBalanced(root) == true) {
        cout<<"true"<<endl;
    } else {
        cout<<"false"<<endl;
    }

    // Tree in example 2
    Node* root2 = newNode(3);
    root2->left = newNode(4);
    root2->right = newNode(8);
    root2->left->left = newNode(5);
    root2->left->right = newNode(9);
    root2->right->right = newNode(7);
    root2->right->right->left = newNode(6);

    if (isBalanced(root2) == true) {
        cout<<"true"<<endl;
    } else {
        cout<<"false"<<endl;
    }
    return 0;
}
true
false

Optimized Approach for Balanced Binary Tree

Modify the height function to return the height of the tree if the tree is satisfied height balance properties else return -1.

  1. The empty tree is always followed height balance(Base Case).
  2. Find the left height by calling the height function recursively, if the height is -1, the left subtree is unbalanced, return -1 immediately.
  3. Find the right height by calling the height function recursively, if the height is -1, the right subtree is unbalanced return -1 immediately.
  4. If the difference between left and right height is less than or equals to 1, return the height(1 + max(leftHeight, rightHeight), else return -1.

Time Complexity = O(n)

JAVA Code

public class BalancedBinaryTree {
    static class Node {
        int data;
        Node left;
        Node right;

        public Node(int data) {
            this.data = data;
            left = right = null;
        }
    }

    // Modified height function
    // Returns the height of tree if the tree is balanced and returns -1 is the tree is not balanced
    private static int height(Node root) {
        if (root == null) {
            // Empty tree is always balanced
            return 0;
        }

        // Find the left height
        int lh = height(root.left);
        if (lh == -1) {
            // Left subtree is unbalanced
            return -1;
        }
        // Find the right height
        int rh = height(root.right);
        if (rh == -1) {
            // Right subtree is unbalanced
            return -1;
        }
        if (Math.abs(lh - rh) <= 1) {
            // Balanced tree, return the height
            return Math.max(lh, rh) + 1;
        }
        // Unbalanced tree
        return -1;
    }

    private static boolean isBalanced(Node root) {
        // Call the modified height function
        int height = height(root);
        if (height == -1) {
            // Unbalanced tree
            return false;
        }
        // Balanced tree
        return true;
    }

    public static void main(String[] args) {
        // Tree in example 1
        Node root = new Node(18);
        root.left = new Node(4);
        root.right = new Node(20);
        root.right.left = new Node(13);
        root.right.right = new Node(70);

        System.out.println(isBalanced(root));

        // Tree in example 2
        Node root2 = new Node(3);
        root2.left = new Node(4);
        root2.right = new Node(8);
        root2.left.left = new Node(5);
        root2.left.right = new Node(9);
        root2.right.right = new Node(7);
        root2.right.right.left = new Node(6);

        System.out.println(isBalanced(root2));
    }
}

C++ Code

#include <iostream>
using namespace std;

class Node {
    public:
    int data;
    Node *left;
    Node *right;
};

// Function to calculate height of a tree rooted at root
int height(Node *root) {
    if (root == NULL) {
        // Empty tree is always balanced
        return 0;
    }
    // Find the left height
    int lh = height(root->left);
    if (lh == -1) {
        // Left subtree is unbalanced
        return -1;
    }
    // Find the right height
    int rh = height(root->right);
    if (rh == -1) {
        // Right subtree is unbalanced
        return -1;
    }
    if (abs(lh - rh) <= 1) {
        // Balanced tree, return the height
        return 1 + std::max(height(root->left), height(root->right));
    }
    // Unbalanced tree
    return -1;
}

// Function to check if given tree is balanced or not
bool isBalanced(Node *root) {
    // Call the modified height function
    int h = height(root);
    if (h == -1) {
        // Unbalanced tree
        return false;
    }
    // Balanced tree
    return true;
}

// Function to allocate new memory to a tree node
Node* newNode(int data) { 
    Node *node = new Node(); 
    node->data = data; 
    node->left = NULL; 
    node->right = NULL;
  
    return (node); 
}

int main() {
  // Tree in example 1
    Node *root = newNode(18);
    root->left = newNode(4);
    root->right = newNode(20);
    root->right->left = newNode(13);
    root->right->right = newNode(70);

    if (isBalanced(root) == true) {
        cout<<"true"<<endl;
    } else {
        cout<<"false"<<endl;
    }

    // Tree in example 2
    Node* root2 = newNode(3);
    root2->left = newNode(4);
    root2->right = newNode(8);
    root2->left->left = newNode(5);
    root2->left->right = newNode(9);
    root2->right->right = newNode(7);
    root2->right->right->left = newNode(6);

    if (isBalanced(root2) == true) {
        cout<<"true"<<endl;
    } else {
        cout<<"false"<<endl;
    }
    return 0;
}
true
false

References

Translate »