Create a binary tree from an array of integers .


Write a function that given an array representation of a binary tree will convert it into a typical tree format.
The following is a visual representation of expected input and output:

Input: [7, 3, 9, 2, 4, 8, 10,11,12,13,14]
Output:
7
/ \
3 9
/\ /\
2 4 8 10

One way to build a tree is that we know that array is like a breadth first traversal . So the series it appears is the same order we need to create tree. Also other property of tree is for a node at index “index” , left child is [2*index+1] and right child is [2*index+2].

public Node createTree(Integer[] array){
        
        if(array == null || array.size == 0)
         return null;
     	Node n = array[0];
     	Queue queue =new Queue();
     	queue.add(n);
        int count = 1;
     	while(count < array.length || !queue.isEmpty()){
     		n.left = new Node(array[count++]);
     		queue.add(n);
                if(count < array.length){
                  n.right = new Node(array[count++])
     		  queue.add(n.right)
               }    	
     	}
     return n;
     }
Advertisements

Program to find whether the binary tree is BST ?


A binary tree is binary search tree (BST) if :

  • If the left subtree nodes value is less than the given node.
  • If the right subtree nodes value is greater than the give node
  • Both the left and right subtrees are BST.

public class BinaryTreeIsBST {

	public boolean IsBST(TreeNode node, int max, int min){

		if(node == null)
			return true;
		if(min < node.value && node.value > max){
			return IsBST(node.left,min,node.value) &&
                         IsBST(node.right,node.value,max);
		}
		return false;
	}
}

Write a program to find whether a binary tree is a balanced ?


As per wikipedia

A balanced binary tree is commonly defined as a binary tree in which the depth of the left and right subtrees of every node differ by 1 or less.

A binary tree can be considered as balanced if

  • The Left subtree is balanced
  • The right subtree is balanced
  • For a node the difference between height of left subtree and right subtree is not more than 1.

One approach to check balance condition for a node is by calculating height of left and right subtree and satisy the 3rd condition,then traverse down the tree to check for each child and keep continuing till you reach the leaf node. If condition is not satisfied for a node return false;

public class IsTreeBalance {


public boolean isBalance(TreeNode root){


if(root == null)

return true;

if (Math.abs(height(root.left)-height(root.right)) >1)

return false;

return isBalance(root.left) && isBalance(root.right);



}

  public int height(TreeNode node){


    if (node == null)

       return 0;
 
    return 1 + Math.max(height(node.left), height(node.right));

  }
}

So far so good. But the problem with this approach is that we visit each node (except root) more than once and hence not the best approach doing top-down check.

Opposite of top-down is bottom-up which is more efficient in this case. We start with leaf node and traverse up the tree. This way a node is visited only once.

public int isBalance1(TreeNode root){

if(root == null)

return 0;

int leftHeight = isBalance1(root.left);

int rightHeight = isBalance1(root.right);

if(Math.abs(leftHeight- rightHeight) > 1)

return -1;

return 1+Math.max(leftHeight, rightHeight);

&nbsp;

}
<pre>

Uninformed Search – BFS and DFS


Breadth first search is a strategy in which root node is expanded first and then all successors are expanded. It means that all the nodes at a given depth are expanded before any other node at the next depth level can be expanded. While expanding the nodes the information of the successors needs to be stored in the memory so that in the next iteration those particular nodes can be expanded.

Binary tree, BFS and DFS traversal

For the given tree the BFS expansion will be :

1 2 3 4 5 6 7 8 9 10 11 12

BFS guarantees to find a path in a tree/graph except for the following conditions:

  • The graph or tree is not cyclic i.e it doesn’t have a curve.
  • A give child node should not have infinite successors. If this happens then the algorithm will be expanding the child node forever.
  • Breadth-first search is complete. This means that if there is a solution breadth-first search will find it regardless of the kind of graph.

DFS(Dept First Search) always continue to expand the deepest node of a first successor till it reaches a leaf node. DFS needs to store only a single path from the root to a leaf node, along with remaining unexpanded sibling nodes for each node on the path. DFS doesn’t guarantee to find a shortest path , because it may happen that it has found a path by expanding the first child but there is an optimal path for some other child of a same parent.

For the given tree the DFS expansion will be:

1 2 5 9 10 6 3 7 11 12 8

Note: left node is given a priority to expand first.

DFS guarantees to find a path ina tree/graph except for the following conditions:

  • The graph or tree is not cyclic i.e it doesn’t have a curve.
  • A give child node should not have infinite successors. If this happens then the algorithm will be expanding the child node forever.

BFS and DFS are called uninformed search which means that it knows only the goal state and start state, to achieve or find the path it simply generates the successors only and doesn’t consider other information like at given time what is the current state, how far is the goal state and what  is the heuristic for the goal state.

Advantage of BFS over DFS is :

  • BFS guarantee’s to give an optimal path for a given tree.
  • BFS generally proves faster than DFS

Advantage of DFS over BFS is :

  • The major advantage DFS has that it take less memory for finding a path than BFS.
BFS DFS
Time O(b^(d+1)) O(b^m)
Space O(b^(d+1)) O(bm)
Optimal Yes No
Complete Yes No

What is difference between iterator access and index access?


Ans) Index based access allow access of the element directly on the basis of index. The cursor of the datastructure can directly goto the ‘n’ location and get the element. It doesnot traverse through n-1 elements.

In Iterator based access, the cursor has to traverse through each element to get the desired element.So to reach the ‘n’th element it need to traverse through n-1 elements.

Insertion,updation or deletion will be faster for iterator based access if the operations are performed on elements present in between the datastructure.

Insertion,updation or deletion will be faster for index based access if the operations are performed on elements present at last of the datastructure.

Traversal or search in index based datastructure is faster.

ArrayList is index access and LinkedList is iterator access.

Program to check rectangle overlapping.


Algorithm : 

  • Two rectangles can overlap if one rectangle has 0,1,2,4 corners inside the other rectangle. The check of above mentioned condition could result is many different combinations. Remember overlapping rectangle cannot have 3 corners inside.
  • Other way we can say that two rectangle overlap if the region of one rectangle lies inside the other.

various overlapping possibilites

  • The best way to find is to identify whether an overlapping area is present or not which can be known if the below mentioned all conditions are true.

If we check that

·        The left edge of B is to the left of right edge of R.

·         The top edge of B is above the R bottom edge.

·         The right edge of B is to the right of left edge of R.

·        The bottom edge of B is below the R upper edge.

Then we can say that rectangles are overlapping.

 

Consider an example: There are two rectangles as shown in diagram – Black Rectangle (B) and Red rectangle(R).

overlap21

 

If we check that

·        The left edge of B  is to the left of  right edge of  R. The selected area will be :

overlap1_11

 

 

·        The top edge of B is above the R bottom edge. So the selected area will be:

overlap2_1

·        The right edge of B is to the right of left edge of R. The selected area will be:

overlap3_11

 

 

 

 

·        The bottom edge of B is below the R upper edge. The selected area will be:

 

overlap4_1

 

Hence all conditions are true we can say that rectangles are overlapping.

Therefore we can see that all the conditions are valid and hence rectangle is overlapping.

 

Below is the source code attached. The logic is only present in checkOverlap() method, rest is used to display the GUI and check.

 

package com;

 

import java.awt.*;

import java.awt.event.*;

 

import javax.swing.*;

 

public class RectangleOverlap extends JPanel{

 

      int r1x1,r1x2,r2x1,r2x2 ;

      int r1y1,r1y2,r2y1,r2y2 ;

            int r1width,r2width ;

            int r1height,r2height ;

      static JButton btn = new JButton(“Check”);

      public RectangleOverlap(int r1x1,int r1y1,int r1x2,int r1y2,int r2x1,int r2y1,int r2x2,int r2y2){

            this.r1x1=r1x1;

            this.r1x2=r1x2;

            this.r1y1=r1y1;

            this.r1y2=r1y2;

            this.r2x1=r2x1;

            this.r2x2=r2x2;

            this.r2y1=r2y1;

            this.r2y2=r2y2;

            r1width = Math.abs(r1x1-r1x2);

            r2width = Math.abs(r2x1-r2x2);

            r1height = Math.abs(r1y1-r1y2);

            r2height = Math.abs(r2y1-r2y2);

            addActionListener();

      }

 

      private void addActionListener() {

            btn.addActionListener(new ActionListener(){

 

                  public void actionPerformed(ActionEvent e) {

                        checkOverlap();

            }

            });

           

      }

      private void checkOverlap() {

            // condition to check whether the rectangles are overlapping or not.s

            boolean isOVerlap= ((r1x2 >= r2x1) &&

                  (r1y2 >= r2y1) &&

                  (r1x1 <= r2x2) &&

                (r1y1 <= r2y2));

     

      if(isOVerlap ){

            JOptionPane.showMessageDialog(null, “OVerlap”);

      }else{

            JOptionPane.showMessageDialog(null, “No OVerlap”);

      }

      }

 

      @Override

      protected void paintComponent(Graphics g) {

            g.drawRect(r1x1,r1y1 , r1width, r1height);

            g.setColor(new Color(123,232,122));

            g.drawRect(r2x1, r2y1, r2width,r2height);

      }

 

      public static void main(String args[]){

            JFrame frame = new JFrame();

            frame.setSize(500,500);

// input to check overlap condition.

// the order followed as : enter coordinate for 1st rectangle as lower limit and upper limit to rectangles          

            frame.getContentPane().add(new RectangleOverlap(20,30,120,130,10,50,160,120),BorderLayout.CENTER);

            frame.getContentPane().add(btn,BorderLayout.SOUTH);

            frame.addWindowListener(new WindowAdapter(){

                  @Override

                  public void windowClosing(WindowEvent e) {

                        System.exit(0);

                  }

                 

            });

            frame.setVisible(true);

      }

}

 

 

How to create customized singly linked list


Linked list work on the concept of FIFO – First in First out. i.e the element inserted first will be the one retrieved first.

Create a class which will act as data structure and act as a single Node.

 public class MyList {

 

            public Object ob;

            public MyList next;

           

            public MyList(Object ob){

                        this.ob=ob;

            }

}

Now create a class to implement the basic functionality:

public class MyLinkedList {

 

            private MyList first=null;

            private MyList last=null;

           

            public MyLinkedList (){

                       

            }

            public void add(Object o){

                        if(first == null){

                                    first = last= new MyList(o);

                        }else{

                                    last.next = new MyList(o);

                                    last= last.next;

                        }

            }

            private void getData(){

                        MyList temp =first;

                        do{

                                    System.out.println(temp.ob + ” “);

                                    temp=temp.next;

                        }while(temp != null);

                       

            }

            private void delete(Object o){

                        MyList temp =first;

                        MyList prev =null;

                       

                        do{

                                    if(temp.ob.equals(o)){

                                                prev.next=temp.next;

                                                break;

                                    }

                                    prev = temp;

                                    temp=temp.next;

                        }while(temp != null);

                       

            }

 

public static void main(String args[]){

                         MyLinkedList lst = new MyLinkedList();

                         lst.add(6);

                         lst.add(62);

                         lst.add(16);

                         lst.add(65);

                         lst.add(26);

                         lst.add(25);

                         System.out.println(“After Insert”);

                         lst.getData();

                         lst.delete(16);

                         System.out.println(“After Delete”);

                         lst.getData();

                         

            }

}

The output will be :

After Insert

6 62 16 65 26 25

 

After Delete

6 62 65 26 25