Find the logical error in the following code

Hi ,

The following code is meant for creating a binary search tree. But however because of the language semantics and the programmers oversight there are logical errors in the code. Try to find the errors if you can.. It takes good understanding of Java to find out the logical errors. All the very best ... 

class MyBinarySearchTreeNode {

    Integer value;
    MyBinarySearchTreeNode left;
    MyBinarySearchTreeNode right;
   
    public MyBinarySearchTreeNode() {
        // TODO Auto-generated constructor stub
        value=null;
        left=null;
        right=null;
       
    }
   
    public MyBinarySearchTreeNode(Integer value) {
        // TODO Auto-generated constructor stub
        this.value=value;
        left=null;
        right=null;
       
    }
   

}

******************************Another class in the same file **************************

public class MyBinarySearchTree{
   
    MyBinarySearchTreeNode rootNode;
   
    public MyBinarySearchTree(){
        rootNode=null;
    }
   
    public void insertNode(MyBinarySearchTreeNode node){
       
        /* check if root node is null
         *
         * if null then its the first node to be inserted .
         *
         * So make it the root the node.
         *
         * */
       
             
        if(rootNode==null){
           
              rootNode=node;
            rootNode.left=null;
            rootNode.right=null;

            return;
        }
       
        /*
         * if root node is not null then we need to traverse the
         *
         * tree to find the appropriate position.
         *
         */
       
        else {
           
                       
            MyBinarySearchTreeNode currNode;
            MyBinarySearchTreeNode nextNode;
           
           
            currNode=rootNode;
            nextNode=null;
           
          
            while(nextNode==null){
               
                             
                            if(node.value<currNode.value){
                                        if(currNode.left!=null){
                    currNode=currNode.left;
                    }
                    else{
                       
                       
                        nextNode=currNode.left;
                                            }
                }
                else if(node.value>currNode.value){
                                        if(currNode.right!=null){
                    currNode=currNode.right;
                    }
                    else{
                                           nextNode=currNode.right;
                                            }
                }
            }
           
                        nextNode=node;
           
           
           
           
        }
       
       
       
       
    }

public static void main(String args[]){
        MyBinarySearchTreeNode node=new MyBinarySearchTreeNode(11);
       
        MyBinarySearchTree btree=new MyBinarySearchTree();
       
        btree.insertNode(node);
       
        for(int i=0;i<10;i++){
           
            System.out.println("\n Enter value for next node");
           
            DataInputStream din=new DataInputStream(System.in);
            int val=0;
            try{
            val=Integer.parseInt(din.readLine());
            }
            catch(Exception e){
                System.out.println("Exception"+e.getMessage());
            }
            node.value=val;
            node.left=null;
            node.right=null;           
            btree.insertNode(node);
        }
       
            }
   
   
}

For clarity below is the description.

MYBinarySearchTreeNode is a class used for representing Nodes.

MyBinarySearchTree class is used for implementing the logic.

Furhter mail method is also written in Tree class.

Finally if you have identified the logical error(s) post it here in the comments section.

Some basics about Trees.

Binary Tree:

A binary tree is a finite set of elements that is either empty or divided into three disjoint sets namely

1.A set containing a single element called root node.
2.A left subtree( can be empty)
3.A right subtree.(can be empty)

So from the above definition , a tree is defined in terms of itself only , recursively.

In a nut shell we can say in a binary tree ea can have atmost two child for each node.Further more the term disjoint plays an important role in the definition of the binary tree. You infer why .

Note that there is no restrictions on the values of the right and left sub-tree in a tree. ( like all those values in left subtree must be less than or equal to root nodes value etc.. )

There are concepts like ancestor,descendant, father, brother etc.. which I am not going to discuss as ;they are analogous to the usual blood relationships and user an easily understand those concepts. Can take it as an excercise.

Before diving into the properties of Binary trees lets see some more definitions .

Level of a node in a binary tree is defined as follows:
1. Level of root node is 0.
2.Level of node n is level of node n's father +1.

Depth of a binary tree is the maximum level of any leaf node in the tree.


Now lets discuss some of the properties of the Binary trees:

Property : The maximum number of nodes at level  'i' in a binary tree is 2ⁱ

Proof:

Induction basis:

We know that the no of nodes at level 0 is 1. i.e root node.

So when n=0  2ⁿ =1

So true for n=0

Induction Hypothesis:

Lets consider that  no of nodes at level K is 2^k for some n=k.

Now we have to show that 2^k+1 is true for n=k+1.

From the inductin hypothesis we have 2^k node at level K. From the definition of binary tree each node can have atmost two children. Therefore at K+1 level , considering each node at level K can have amost two children,

no of nodes at level K+1 <=2^K *2
                                       <=2^K+1

Hence proved.



Property:

The maximum no of nodes in a binary tree of depth K is 2^K+1-1.

Proof:

from the above proof maximum no of nodes at level k is 2^k , at K-1 is 2^k-1 ....

total no of nodes is <=2^k+2^k-1+... +2⁰
                              <=2^k+1-1 ( By induction we can prove this )


 Property:

For any non-empty binary tree T, if n0 is the no. of leaf nodes & n2 is the no. of nodes of degree 2, then n0 = n2 + 1.

Proof:Let n be the total no. of nodes in binary tree.

            n0 no. of nodes of degree 0

            n1  no. of nodes of degree 1

            n2  no. of nodes of degree 2

                        n = n0 + n1 + n2  -----> (1)

            All the nodes except the root node has a branch coming into it. Let B be the no. of branches in the binary tree.

                        n = B + 1 ----->(2)

                        B = 0.n0 + 1 * n1 + 2*n2 since there would be 0 branches from n0, and 1 branch from n1 nodes and two branches from n2 nodes

                        B = n1 + 2n2    ---->3

            Substituting (3) in (2).

                        n =  n1 + 2n2 + 1  ----> 4.

            Equate 1 & 4

                        n0 + n1 + n2 = n1 + 2n2 + 1

                        n0 = n2 + 1

Proved.

Strictly Binary Tree:
If every non leaf node in a binary tree has non empty left and right sub trees, then the tree is termed as strictly binary tree.

So , from the definintion , it is evident that strictly binary tree contains nodes of degree 2 or 0 but not 1.

Property:

The strictly binary tree with n leaf nodes contains 2n-1 nodes.

Proof:

Let number of nodes in Strictly binary tree be N.

Then N=n0+n1+n2. where n0,n1 and n2 are no of nodes of degree 0,1 ad 2 respectively.

From the definition of Strictly binary tree n1=0. as there wont be any nodes of degree 1.

==> N=n0+n2.

From the property of binary trees n0=n2+1.

==> N=n0+n0-1

==> N=2n0-1

if we consider no of leaf nodes =n this implies n=n0.

therefore N=2n-1.

Hence proved.

Complete Binary tree or full Binary tree:

A complete binary tree of depth d is the strictly binary tree all of whose leaves are at level d. That is in Complete binary tree only nodes of degree 2 or 0 exist . further more all leaves would be at the same level .

As we have seen , in a binary tree with depth d, the maximum possible no of nodes is pow(2,d+1)-1 ( proved above) the maximum case occurs when the binary tree is a complete binary tree.

So when given the depth of full binary tree we compute the no of nodes as pow(2,d+1)-1.

Given the no of nodes we can compute the depth as log(n+1) -1 in base 2.




 

Two stacks in a single array-- simulation

Hi All,

The topic of discussion for today is implementing two stacks in a single array.

package algorithms;

public class TwoStacksInASingleArray {

    int stack[];
   
    /* for two stacks*/
    int top1,top2;
   
    /* logic two stacks grow in opposite directions. One upwards one downwards*/
   
    public TwoStacksInASingleArray(int size){
        stack=new int[size];
       
        top1=-1;
       
        top2=size;
    }
   
   
   
    public static void  main(String args[]){
       
        TwoStacksInASingleArray tst=new TwoStacksInASingleArray(10);
       
        tst.push1(1);
        tst.push2(2);
        tst.push1(3);
        tst.push2(4);
        tst.push1(5);
        tst.push1(6);
        tst.push1(7);
        tst.push1(8);
        tst.push1(9);
        tst.push2(10);
        tst.display();
       
        tst.pop1();
        tst.pop2();
        tst.pop1();
        tst.pop1();
        tst.pop1();
        tst.pop1();
        tst.pop2();
        tst.pop2();
        tst.pop2();
        tst.pop2();
        tst.pop1();
        tst.pop1();
        tst.pop1();
       
        //tst.display();
       
        tst.push1(9);
        tst.push2(10);
        tst.display();
       
    }
   
   
    public void push1(int value){
       
        /* check if stack is already full*/
       
        if(isStack1Full()){
            System.out.println("\n stack1 is full");
        }
        else{
            top1++;
           
            stack[top1]=value;
        }
       
       
    }
   
   
public void push2(int value){
       
        /* check if stack is already full*/
       
        if(isStack2Full()){
            System.out.println("\n stack2 is full");
        }
        else{
            top2--;
           
            stack[top2]=value;
        }
       
       
    }

public int pop1(){
   
    /* check for underflow*/
   
    if(isStack1Underflow()){
        System.out.println("\nStack1 Underflow");
        return -1;
    }
    else{
        int ret=stack[top1];
        System.out.println("\n Popped element is "+ret);
       
        stack[top1--]=0;
        return ret;
    }
}


public int pop2(){
   
    /* check for underflow*/
   
    if(isStack2Underflow()){
        System.out.println("\nStack2 Underflow");
        return -1;
    }
    else{
        int ret=stack[top2];
        System.out.println("\n Popped element is "+ret);
       
        stack[top2++]=0;
        return ret;
    }
}
   
    boolean isStack1Full(){
        if(top1==stack.length-1){
            return true;
        }
        else if(top1+1==top2){
            return true;
        }
        else{
            return false;
        }
    }
   
   
    boolean isStack2Full(){
        if(top2==0){
            return true;
        }
        else if(top2-1==top1){
            return true;
        }
        else{
            return false;
        }
    }
   
   
    public boolean isStack1Underflow(){
       
        if(top1==-1){
            return true;
        }
        else{
            return false;
        }
    }
   
public boolean isStack2Underflow(){
       
        if(top2==stack.length){
            return true;
        }
        else{
            return false;
        }
    }
   
    public void display(){
       
        for(int i:stack){
            System.out.println(i+"\n");
        }
    }
   
}

From the above code it is evident that one stack with top1 is growing upwards, while the other with top2 is growing downwards. Rest is similar to the usual single stack using an array except the conditions for underflow and overflow will be little changed as shown to include for the other stack.

As is the case always you can still improve the above algorithm as an exercise . If you do so kindly post it here. It could be helpful to someone.

Thanks in advance .

Cheers .

Subbu.

Stacks-- parenthesis matching

Hi All,

Today our topic of discussion is checking the correctness of parenthesis I mean matching right and left parenthesis using stack.

static Stack<Character> s=new Stack<Character>();

   

   

    public static void main(String[] args) {

        // TODO Auto-generated method stub

       

       

        boolean hasMoreChars=true;

       

        char nextChar='A';

        DataInputStream din=new DataInputStream(System.in);

        while(hasMoreChars){

            try{

                System.out.println("\n Enter a character");

            nextChar=(din.readLine()).charAt(0);

           

            System.out.println(nextChar);

            }

            catch (Exception e) {

                // TODO: handle exception

                e.printStackTrace();

                System.exit(0);

            }

           

            if(nextChar==-1){

                System.out.println("in If\n");

                hasMoreChars=false;

            }

           

            else{

                System.out.println("\n In else");

            if(nextChar=='('||nextChar=='{'||nextChar=='['){

               

                System.out.println("\n In push");

                s.push(nextChar);

            }

            else if(nextChar==')'||nextChar=='}'||nextChar==']'){

               

                System.out.println("\n In pop");

                if(s.isEmpty()){

                    System.out.println("\n there is a mismatch");

                }

               

                else{

                if(nextChar==')'){

                    if(s.pop()=='('){

                        continue;

                       

                    }

                    else{

                        System.out.println("\n there is a mismatch");

                    }

                }

               

                if(nextChar=='}'){

                    if(s.pop()=='{'){

                        continue;

                       

                    }

                    else{

                        System.out.println("\n there is a mismatch");

                    }

                }

               

                if(nextChar==']'){

                    if(s.pop()=='['){

                        continue;

                       

                    }

                    else{

                        System.out.println("\n there is a mismatch");

                    }

                }

               

            }

           

           

        }

    }

   

   

   

}

    }

for the purpose focusing on the problem at hand , not on stack, I have used the stack class in util.  Further more there are some minor mistakes in the above code. It is left for your to find out the mistakes and rectify them as an execercise.

Arrays using stacks.

Hi all,

The following code is for implementing array structure using stacks.The implementation is not complete (it doesnt include runtime exception checkings etc) to focus more on logic rather than validations.

package algorithmProblems;

import java.util.Stack;

public class ArrayUsingStack {
   
   
    public static void main(String args[]){
    Array2 ar=new Array2(10);
   
    ar.disp();                       
    ar.set(11, 5);
    ar.disp();
   
    System.out.println(ar.get(4));
    }
}

class Array2{
   
    Stack s1,s2;
    Array2(int size){
        s1=new Stack();
        s2=new Stack();
        s1.setSize(size);
        s2.setSize(size);
        System.out.println(s1.size());
        for(int i=0;i<s1.size();i++){
            s1.set(i,i);/* instead you can create a method initialize and call it in constructor.. actually we shouldnt use this set method . I have used for clarity */
           
        }
}
   
    public void add(int value){
        s1.push(value);
    }
   
    public Object get(int index){
        int diff=s1.size()-index;
        int ret=0;
       
       
        for(int i=0;i<diff;i++){
           
            s2.push(s1.pop());
           
           
        }
        ret=(Integer)s1.peek();
        for(int i=0;i<diff;i++){
            s1.push(s2.pop());
        }
        return ret;
    }
   
    public void disp(){
        System.out.println(s1);
    }
   
    public void set(int index,int value){
       
        if(index>s1.size()){
            System.out.println("Array Index out of Bounds");
            return;
        }
        int diff=s1.size()-index;
        System.out.println(s1);
        for(int i=0;i<diff+1;i++){
            s2.push(s1.pop());
        }
        s1.push(value);
        for(int i=0;i<diff;i++){
            s1.push(s2.pop());
        }
       
       
       
    }
   
}

From the above program the logic is clear we need to copy some elements to another stack and perform the operation and then again push the elements back to original stack. You can add further operations/validations as an excercise.

Kth Largets element in an sorted array.

Hi All,

For today the problem statement is this :

Find the Kth largest element in a sorted array.

Solutions:

Lets for the sake of simplicity  consider the array is in descending order.Futher duplicates are possible.

Below is one of the possible solutions :

Go through each element in the sorted , copy each non-repeated element to a different array. At the end Kth largest element is copy[k-1] element.

int []sortedArray={10,9,9,8,6,5,5,3,3,2,1};

       

        int k=3;

        /*                 logic

         *

         * 1. Copy each different integer to a new array.

         * 2. Now the Kth largest element would be

         *         a) a[k-1] if in descending order

         *         b) a[length-k-1]

         *

         *

         * */

       

        int []copy=new int[sortedArray.length];

        /* the problem with this approach is we dnt know how many duplicates are there*/

        int j=1;

        copy[0]=sortedArray[0];

       

        for(int i=1;i<sortedArray.length;i++){

            if(sortedArray[i]!=sortedArray[i-1]){

                copy[j++]=sortedArray[i];

            }

        }

       

        for(int i:copy){

            System.out.println(i);

        }

       

        /* now the Kth largest element is copy[K-1]*/

       

       

        System.out.println(k+"th largest element is :"+copy[k-1]);

       

Now lets discuss the implications of this scheme.

We have used an auxiliary array named copy[] . As we dont know before hand how many different non-repeated element exists in the array we need to create the copy with that of the size of the original array.

Lets say the size of the original array is 1 million ... its too bad approach . It needs O(N) augmented space (apart from space for the original array).

We will also see time complexity for the above algorithm . Meanwhile I found the follwing links interesting

http://pages.cs.wisc.edu/~vernon/cs367/notes/3.COMPLEXITY.html

The point to be noted there in the notes is that we see how scalable our algorithm with the input size !!.Which algorithm runs faster is secondary and requires more details  .

Now we analyze our code:

for(int i=1;i<sortedArray.length;i++){

            if(sortedArray[i]!=sortedArray[i-1]){

                copy[j++]=sortedArray[i];

            }

        }

lets say  the bit of code   if(sortedArray[i]!=sortedArray[i-1]){

                copy[j++]=sortedArray[i];

            }

takes a constant time K . That is it is O(1).

So the time complexity is O(N*1) =O(N). In all the cases.

Clearly from the analysis of space and time complexity this approach is not sufficient.

Now lets look for some other way.

In the following code we maintain a counter to count the no of different values that we have read so far in the array. The point here is we would like to see the Kth value i.e counter=K.

 */
        int []sortedArray={10,9,9,8,6,5,5,3,3,2,1};
       
        int k=3;
       
        int count=1;
       
        for(int i=1;i<sortedArray.length;i++){
           
            if(sortedArray[i]!=sortedArray[i-1]){
                count++;
               
            }
           
            if(count= =k){
                System.out.println(sortedArray[i]);
                break;
            }
               
           
           
           
        }

the beauty of the above code is evident . We dont need any auxiliary memory . The space complexity is O(N) for the original array only.

Now coming to the time complexity the worst case time complexity remains the same , assuming all preliminary operations take constant time, which is O(N). However the best case and worst case scenarios are promising than the previous approach.

Still we are not satisfied with the worst case performance as it is O(N) . We need more good approaches.

To be continued in next post .

Request  : Kindly give your valuable suggestions and comments on the content. Feel free to debate about the content.

 

Introduction

Hi All,

In this blog I will be discussing various algorithms and data structures . Kindly give your feedback always.

Thanks and Regards
Subrahmanyam K.