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 val, TreeNode left, TreeNode 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;
}

Find integer from string and sum of them

• Example 1:

Input:  jh2gv1b78bm9
Output: 2+1+7+8+9= 27

• Approach 1:

        Java

public class SumInt

{

 public int sumInt(String str) {

        int aa = 0;

        for (int i = 0; i < str.length(); i++) {

            int xx = (int) str.charAt(i);

            String zz = "" + str.charAt(i) + "";

            if (xx > 47 && xx < 58) {

                aa += Integer.parseInt(zz);

            }

        }

        return aa;

    }

    public static void main(String args[]) {

        String str= "jh2gv1b78 bm9";

        SumInt obj = new SumInt();

       int a = obj.sumInt(str);

        System.out.println(a);

    }

}

Find indices of the two numbers such that they add up to the target in the given array

Write a program to Find indices of the two numbers such that they add up to the target in the given array

Example

Input:  [1,0,5,3,6,8], targer=9
Output: [0,4] or [1,5]

Approach

Java

import java.util.ArrayList;
import java.util.Arrays;
import java.util.Collections;
import java.util.Comparator;
import javafx.util.Pair;
public class TwoSum {
    public static void main(String aa[]) {
        TwoSum s = new TwoSum();
        int[] nums = { 1, 0, 5, 3, 8, 9 };
        int target = 9;
        int result[] = s.twoSum(nums, target);
        System.out.println(Arrays.toString(result));
        // [1,5]
    }
    public int[] twoSum(int[] nums, int target) {
        ArrayList<Pair<Integer, Integer>> l = 
                new ArrayList<Pair<Integer, Integer>>();
        for (int i = 0; i < nums.length; i++) {
            Pair p = new Pair(nums[i], i);
            l.add(p);
        }
        // sort Pair of array list based on key
        Collections.sort(l, new Comparator<Pair<Integer, Integer>>() {
            @Override
            public int compare(final Pair<Integer, Integer> o1, 
                    final Pair<Integer, Integer> o2) {
                return o1.getKey() - o2.getKey();
            }
        });
        int sP = 0, lP = nums.length - 1;
      while (sP < lP) {
        if ((l.get(sP).getKey() + l.get(lP).getKey()) == target) {
         return new int[] { l.get(sP).getValue(), l.get(lP).getValue() };
      } else if ((l.get(sP).getKey() + l.get(lP).getKey()) > target) {
         lP--;
       } else {
         sP++;
        }
    }
   return null;
    }
}

                 

Check given number is prime number

Write a program to check if the given number is prime or not.

Prime Number: A number that is divisible by 1 and itself is a prime number.

Note: 1 is not a prime number.

Example:

Input: 13
Output: 13 is prime number
Explanation: If number only divisible by 1 and itself then number is prime.

Approach: Iterate till n-1 if the number is divisible by any number then the number is not prime, else the number is prime.

C

#include <stdio.h>
int main()
{
    int n = 13;
    if (n <= 1)
        printf("Number is not prime ");
    else
    {
        int flag = 0;
        for (int i = 2; i < n; i++)
        {
            if (n % i == 0)
            {
                flag = 1;
                break;
            }
        }
        if (flag == 0)
        {
            printf("Number is prime ");
        }
        else
        {
            printf("Number is not prime ");
        }
    }
    return 0;
}

Java

public class CheckIsPrime{
     
  public static void main(String[] args) {
    int number=13;
    if(number>1 && checkIsPrime(number))
    System.out.println(number+" is prime number");
    else
    System.out.println(number+" is not prime number");
  }
//Method to check prime number
  private static boolean checkIsPrime(int number) {
    
    for(int i=2;i<number;i++)
       {
 // If a number is divisible by any number from 2 to n-1
 // then it is not a prime
         if(number%i==0)
           return false;
       }
     return true;
  }
}
//Time Complexity:O(n)
//Space Complexity:O(1)

C++

#include <bits/stdc++.h>
using namespace std;
//Function to check for prime numbers
bool checkPrime(int n)
{
  if(n==1)
    return false;
  for(int i=2;i<n;i++)
    {
     //If a number is divisible by
     // any number from 2 to n-1
     // then it is not a prime
      if(n%i==0)
        return false;
     }
   return true;
}
int main()
{
   int n=13;
   if(checkPrime(n))
      cout<<n<<" is a prime\n";
   else
      cout<<n<<" is not a prime\n";
}

//Time Complexity :O(n)
//Space Complexity:O(1)