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;
	}
}

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

 

 

Program to find height of a binary tree


The algorithm works as follows:

  • Each node starting from the parent node is push into an stack. Then the element is popped from the stack and a check is made to find whether the node has left and right child. If any one or both are present the elements are pushed into stack. At the same time a corresponding entry is made into a map with key as ‘node’ and value as the ‘height’ .The value of height is one more than the height of parent and intial height of parent is set to 1.

The code flow is explained below.

  • The program contains two classes : Node and BinaryTree class. The Node class is a datastructure used to build a tree and BinaryTree is a class to find the height.
  • The class Node is a data structure which can have left child (Node), a right child (Node) and can contain any value.

package com.src;

public class Node {

 

private Node left;

private Node right;

private Object value;

 

public Node getLeft() {

return left;

}

 

public Node getRight() {

return right;

}

 

public Object getValue() {

return value;

}

 

public Node(Node left, Node right, Object value) {

super();

this.left = left;

this.right = right;

this.value = value;

}

}

 

The BinaryTree class contains the logic of finding the height of the tree.

Consider the following example:

tree2

  • The createTree() method is used to create the node for each element in tree. Create node starting from the leaf node and moving upward. For above tree:

Node node21 = new Node(null,null,21);

Node node1 = new Node(null,node21,1);

  • For the given example the createTree() method will have code as:

private void createTree(){

Node node21 = new Node(null,null,21);

 

Node node23 = new Node(null,null,23);

Node node56 = new Node(null,null,56);

Node node11 = new Node(null,null,11);

Node node1 = new Node(null,node21,1);

Node node45 = new Node(node23,node1,45);

Node node73 = new Node(null,null,73);

Node node12 = new Node(node56,node11,12);

 

Node node34 = new Node(node45,node73,34);

Node node87 = new Node(node12,null,87);

 

Node node77 = new Node(node34,node87,77);

parent = node77;

}

 

The logic for finding height is put in getHeight() method:

private Node parent = null;

     private Stack<Node> stack = new Stack<Node>();

// the map will store the node and its current height

     private Map<Node,Integer> map = new

HashMap<Node,Integer>();    

 

private void getHeight(){

 

int highest_height =1;

int current_height = 1;

int parent_height=0;

Node temp_node = null;

stack.push(parent); // initially only the parent is present in stack

map.put(parent, current_height);

while(stack.size() != 0){

 temp_node = stack.pop();  // pop element at top from stack.

parent_height = map.get(temp_node);  // get the height

if(temp_node.getLeft() != null){  // if current node has left child

 current_height = parent_height+1; // increase the height by 1

stack.push(temp_node.getLeft()); // push the element to the stack

//put into map – put(current node, current height)

map.put(temp_node.getLeft(),current_height);   

 highest_height= (highest_height < current_height) ? current_height : highest_height;

}

 

if(temp_node.getRight() != null){  // same as left child

current_height =parent_height+1;

map.put(temp_node.getRight(),current_height);

stack.push(temp_node.getRight())     

 highest_height= (highest_height < current_height) ? current_height : highest_height;

    

}

    

System.out.println(“\n Elements currently in stack \n”);

         

for(int i =0; i<stack.size();i++){

System.out.print(” “ +((Node)stack.get(i)).getValue());  

     }

             

}

         

System.out.println(“The height is “ + highest_height);

   }

    

public static void main(String[] args) {

           BinaryTree bt = new BinaryTree();

          bt.createTree();

          bt.getHeight();

 

     }

 

}

 

The logs will show:

 

Elements currently in stack 34 87

Elements currently in stack 34 12

Elements currently in stack 34 56 11

Elements currently in stack 34 56

Elements currently in stack 34

Elements currently in stack 45 73

Elements currently in stack 45

Elements currently in stack 23 1

Elements currently in stack 23 21

Elements currently in stack 23

Elements currently in stack

The height is 5

 

 

 

  • When the parent is pop from the stack a check is made to find whether it has a left child or not, if a left child is present push the left child to stack, also put the same element in a map with key as the current node and value is height which is incremented by 1 of its parent height.
  • Now check if the current height is greater than the highest height or not. If it is set the highest_height to current_height.
  • Similarly it works for the right child.

For given example when a check is made for parent, then 34 and 87 are push into stack.

 

Elements currently in stack 34 87 

  • Now 87 is picked up and a check is made for it. Since it contains only left child as 12 , the current stack will look like

 Elements currently in stack 34 12

  • The while loop iterates till the stack becomes empty.
  • The main overhead in this program is to create a tree like structure by declaring the nodes explicitly.