Balanced Binary Tree

Write a program to check the binary tree is a balanced binary tree or not.

Example:

Input:  tree=[3,7,8,5,6,null,null]
Output: Tree is balanced

Approach

Java 

public class BalanceTree {
    public static void main(String[] args) {
        TreeNode tree = new TreeNode(1);
        tree.left = new TreeNode(9);
        tree.right = new TreeNode(20);
        tree.right.left = new TreeNode(15);
        tree.right.right = new TreeNode(7);
        tree.right.right.right = new TreeNode(18);

        BalanceTree bt = new BalanceTree();
        if (bt.isBalanced(tree))
            System.out.println("Tree is balanced");
        else
            System.out.println("Tree is not balanced");
    }
    public boolean isBalanced(TreeNode root) {

        if (root == null)
            return true;

        int lh = nHeight(root.left);
        int rh = nHeight(root.right);

        if (Math.abs(lh - rh) <= 1 && 
isBalanced(root.left) && isBalanced(root.right)) {
            return true;
        }
        return false;
    }

    public int nHeight(TreeNode node) {
        if (node == null)
            return 0;

        int lh = nHeight(node.left);
        int rh = nHeight(node.right);

        return 1 + Math.max(lh, rh);

    }
}

class TreeNode {
    int val;
    TreeNode left;
    TreeNode right;
    TreeNode() {
    }
    TreeNode(int val) {
        this.val = val;
    }
    TreeNode(int valTreeNode leftTreeNode right) {
        this.val = val;
        this.left = left;
        this.right = right;
    }
}


C++

#include <bits/stdc++.h>
using namespace std;
//struct for treenode
struct TreeNode{
    int data;
    TreeNode *left;
    TreeNode *right;
    TreeNode(int data)
    {
        this->data=data;
        this->left=NULL;
        this->right=NULL;
    }
};
//Function to find the height
//of the tree
int height(TreeNode *root)
    {
        if(root==NULL)
              return 0;
        //left height
        int lefth=height(root->left);
        //right height
        int righth=height(root->right);
        if(lefth>righth)
               return lefth+1;
        return righth+1;
    }
//Fucntion to check the tree is 
//height balanced or not
bool isBalanced(TreeNode* root) {
        if(root==NULL)
              return true;
        //left height
        int lefth=height(root->left);
        //right height
        int righth=height(root->right);
        if(abs(lefth-righth)>1)
               return false;
        return isBalanced(root->left)&&isBalanced(root->right);
    }
int main()
{
    TreeNode *tree=new TreeNode(3);
    tree->left=new TreeNode(9);
    tree->right=new TreeNode(20);
    tree->right->left=new TreeNode(15);
    tree->right->right=new TreeNode(7);
    bool flag=isBalanced(tree);
    if(flag)
       cout<<"Tree is balanced\n";
    else
      cout<<"Tree is not balanced\n";
    return 0;
}


No comments:

Post a Comment