Wednesday, December 31, 2014

Algorithm to find the first common ancestor of two nodes in a binary tree.

Q. Design an algorithm and write code to find the first common ancestor of two nodes in a binary tree. Avoid storing additional nodes in a data structure. NOTE: This is not necessarily a BST.

Algorithm

1. With link to parent node -

Start with any of the two nodes (lets say p). Travel up look at all the nodes in the other branch of the node if there is any. If you find the second node q, then the current node whose left or right child was being searched is the common ancestor.

If, however, you don't find the other node, start with the second node q and repeat the same procedure. If you find p travelling up (since if p did not find q on it's way up, it must be beneath it), then p's parent is the common ancestor (or p if you define a common ancestor that way). If p isn't found, and q reaches the tree's root, p isn't there in the tree.

Whether a node is in the tree or not can be tested by travelling up until you find the root node matching with the root node of the tree you have.

2. Without link to parent node - 

Check if left or right of root has p/q.
If p is found and q isn't return p and the opposite for the other case.
If p is found in left and q in right or the opposite case, then current node is the common ancestor.
If p and q are found on the same side, repeat the procedure for that the current node's child which is there at that side (left or right).

Source:

class WithoutParentFieldM2{
    public class Node{
        int value;
        Node left, right;
        Node(){}
        Node(int value){this.value = value;}
        Node(int value, Node left, Node right){
            this.value = value;
            this.left = left;
            this.right = right;
        }
        
        @Override
        public String toString(){
            return "Value: "+value;
        }
    }
    
    class Result{
        public Node node;
        public boolean isAncestor;
        public Result(Node n, boolean isAnc){
            node = n;
            isAncestor = isAnc;
        }
    }
    
    Result commonAncestorHelper(Node root, Node p, Node q){
        if(root == null)return new Result(null, false);
        if(root == p && root == q)return new Result(root, true);
        Result rx = commonAncestorHelper(root.left, p, q);
        if(rx.isAncestor)return rx;
        Result ry = commonAncestorHelper(root.right, p, q);
        if(ry.isAncestor)return ry;
        if(rx.node!=null && ry.node!=null){
            return new Result(root, true);
        }else if(root==p||root == q){
            boolean isAncestor = rx.node != null || ry.node!=null ;
            return new Result(root, isAncestor);
        }else return new Result(rx.node!= null?rx.node:ry.node, false);
    }
    
    Node commonAncestor(Node root, Node p, Node q){
        Result r = commonAncestorHelper(root, p, q);
        if(r.isAncestor){
            return r.node;
        }
        return null;
    }
    
    Node root;
    Node node1, node2;
    void makeCustomTree(){    
        //Test Case: 3
        root = new Node(35);
         
        root = new Node(35);
        root.left = new Node(15);
        root.left.left = new Node(7);
        root.left.left.left = new Node(4);
        root.left.left.right = new Node(9);
        root.left.right = new Node(20);
        root.left.right.left = new Node(17);
        root.left.right.right = new Node(34);
        root.right = new Node(55);
        root.right.left = new Node(40);
        node1 = root.right.left.left = new Node(37);
        root.right.left.right = new Node(50);
        root.right.right = new Node(60);
        node2 = root.right.right.left = new Node(57);
        root.right.right.right = new Node(65);
    }    
    
    public static void main(String[] args){
        WithoutParentFieldM2 tree = new WithoutParentFieldM2();
        tree.makeCustomTree();
        System.out.println(tree.commonAncestor(tree.root, tree.node1, tree.node2));
    }
}

class WithoutParentFieldM1{
    public class Node{
        int value;
        Node left, right;
        Node(){}
        Node(int value){this.value = value;}
        Node(int value, Node left, Node right){
            this.value = value;
            this.left = left;
            this.right = right;
        }
        
        @Override
        public String toString(){
            return "Value: "+value;
        }
    }
    
    boolean found;
    
    class Result{
        boolean present = false;
        Node node;
    } 
    
    void preOrder(Node nodeToFind, Node node){
        if(node == null) return; 
        if(node == nodeToFind)found = true;
        if(found) return;
        preOrder(nodeToFind, node.left);
        if(found)return;
        preOrder(nodeToFind, node.right);
    }
    
    boolean find(Node nodeToFind, Node node){
        found = false;
        preOrder(nodeToFind, node);
        return found;
    } 
    
    Node check(Node n1, Node n2){
        if(n1==null && n2 == null)return null;
        
        //Check if n1 and n2 are in the tree or not
        boolean n1InLeft = find(n1, root.left), n1InRight;
        if(n1InLeft)n1InRight = false;else n1InRight = find(n1, root.right);
        
        boolean n2InLeft = find(n2, root.left), n2InRight;
        if(n2InLeft)n2InRight = false;else n2InRight = find(n2, root.right);
         
        //If n1 is there and n2 isn't return n1
        //If n2 is there and n1 isn't return n2
        if((n1InLeft || n1InRight) && !n2InLeft && !n2InRight)return n1;
        else if((n2InLeft || n2InRight) && !n1InLeft && !n1InRight)return n2;
        
        //First case has been tested already to find n1 and n2
        if(n1InLeft == n2InRight)return root;
        
        //Go check left or right - root has already been checked
        if(n1InLeft && n2InLeft)return check(root.left, n1, n2);
        else return check(root.right, n1, n2);
    }
    
    Node check(Node node, Node n1, Node n2){ 
        if(node == null)return null;
        boolean n1InLeft = find(n1, node.left);
        boolean n2InRight = find(n2, node.right);
        
        if(n1InLeft && n2InRight){return node;}
         
        if(n1InLeft && !n2InRight){return check(node.left, n1, n2);}
        else {return check(node.right, n1, n2);} 
    }
     
    Node root;
    Node node1, node2;
    void makeCustomTree(){    
        //Test Case: 3
        root = new Node(35);
         
        root = new Node(35);
        root.left = new Node(15);
        root.left.left = new Node(7);
        root.left.left.left = new Node(4);
        root.left.left.right = new Node(9);
        root.left.right = new Node(20);
        root.left.right.left = new Node(17);
        root.left.right.right = new Node(34);
        root.right = new Node(55);
        root.right.left = new Node(40);
        node1 = root.right.left.left = new Node(37);
        root.right.left.right = new Node(50);
        root.right.right = new Node(60);
        node2 = root.right.right.left = new Node(57);
        root.right.right.right = new Node(65);
    }    
    
    public static void main(String[] args){
        WithoutParentFieldM1 tree = new WithoutParentFieldM1();
        tree.makeCustomTree();
        System.out.println(tree.check(tree.node1, tree.node2));
    }
}

public class WithParentField {
    
    public class Node{
        int value;
        Node left, right, parent;
        Node(){}
        Node(int value){this.value = value;}
        Node(int value, Node left, Node right){
            this.value = value;
            this.left = left;
            this.right = right;
        }
        
        @Override
        public String toString(){
            return "Value: "+value;
        }
    }
    
    boolean found;
    
    void preOrder(Node nodeToFind, Node node){
        if(node == null) return; 
        if(node == nodeToFind)found = true;
        if(found) return;
        preOrder(nodeToFind, node.left);
        if(found)return;
        preOrder(nodeToFind, node.right);
    }
    
    boolean presentInThisSubtree(Node nodeToFind, Node node){
        found = false;
        preOrder(nodeToFind, node);
        return found;
    }
    
    Node findAncestor(Node n1, Node n2){
        if(n1==null || n2 == null)return null;
        boolean n1PresentInTree = false, n2PresentInTree = false;
        Node parent = n1.parent; 
        
        Node previous = n1; 
       
        while(!found && parent != null && parent!=n2){ 
            if(previous == parent.left){presentInThisSubtree(n2, parent.right);}
            else presentInThisSubtree(n2, parent.left);
            previous = parent;
            parent = parent.parent;
        } 
        if(parent==n2 || found){
            /*
                In case n1 and n2 are in a subtree but that subtree 
                is not a subtree of the tree that we have
            */
            while(parent!=null && parent!=root)parent=parent.parent; 
            if(parent == root){if(found)return previous;else return n2.parent;}  
        }else{
            if(previous == root)n1PresentInTree = true;
            parent = n2.parent;
            if(parent!=null)while(parent.parent!= null && parent!=n1)parent = parent.parent;
            if(parent == n1)return n1.parent;
            else if(parent == root){ 
                System.out.println("Node 1 not present, Node 2 present");return n2;} 
            else if(n1PresentInTree){
                System.out.println("Node 1 present, Node 2 not present");return n1;}
        } 
        System.out.println("Node 1 and Node 2 not present");
        return null;
    }
    
    
    
    Node root;
    Node node1, node2;
    void makeCustomTree(){    
        //Test Case: 3
        root = new Node(35);
        
        node1 = new Node(4);
        node2 = new Node(65);
        
        addChildren(root, new Node(15), new Node(55));
        addChildren(root.left, new Node(7), new Node(20));
        addChildren(root.right, new Node(40), new Node(60));
        addChildren(root.left.left, node1, new Node(9));
        addChildren(root.left.right, new Node(17), new Node(34));
        addChildren(root.right.left, new Node(37), new Node(50));
        addChildren(root.right.right, new Node(57), node2); 
        
        
        Node root2 = new Node(22);
        node1 = new Node(11);
        node2 = new Node(33);
        addChildren(root2, node1, node2);
//        node1 = new Node(222);
//        node2 = new Node(444);
    }   
    
    void addChildren(Node parent, Node left, Node right){
        parent.left = left;
        parent.right = right;
        if(left!=null) left.parent = parent;
        if(right!=null) right.parent = parent;
    }
    
    public static void main(String[] args){
        WithParentField tree = new WithParentField();
        tree.makeCustomTree(); 
        Node node3 = tree.new Node(33);
        System.out.println(tree.findAncestor(tree.node1, tree.node2));
    }
}

Output:

WithParentField.class
Node 1 and Node 2 not present
null

WithoutParentFieldM1.class
Value: 55

WithoutParentFieldM2.class
Value: 55

Tuesday, December 30, 2014

Finding the in-order successor of a given Node of a Binary Tree.

Q. Write an algorithm to find the 'next' node (i.e., in-order successor) of a given node in a binary search tree. You may assume that each node has a link to its parent.

Algorithm:

Four cases:

Case 1:  Node is root or is the last Node in in-order traversal. (return null).
                                                                                                                                 
 Case 2: Node (1) doesn't have a right child and is the left child of it's parent. (return 2)

 Case 3: Node(4) Does not have a right child and is the right child of it's parent. (return 4)
Case 4: Node(2) has a right child. (return 7)







1. Check if there is a right node. If there is a right node, go to it's farthest left and return that node. If there was no left node in the first place, return that right node.

2. If there is no right node, go back up. Now if the previous node was a left child, print parent else keep going up.

3. If you reach null, there is no left child in the path (in Case 1) print null.


Source:
public class Code{
    
    public class Node{
        int value;
        Node left, right, parent;
        Node(){}
        Node(int value){this.value = value;}
        Node(int value, Node left, Node right){
            this.value = value;
            this.left = left;
            this.right = right;
        }
        
        @Override
        public String toString(){
            return "Value: "+value;
        }
    }
    
    //Function Required
    Node getInorderSuccessor(Node node){
        if(node == null)return null;
        Node prev;
        if(node.right != null){
            node = node.right;
            while(node.left!=null)node= node.left;
            return node;
        }
        prev = node;
        node = node.parent; 
        while(node!= null && prev!=node.left){
            prev = node;
            node = node.parent;
        }
        return node;
    }
     
    Node root;
    Node test;
    void makeCustomTree1(){
        //Test Case: 1
        root = new Node(2);
        test = root;
    }
        
    void makeCustomTree2(){
        //Test Case: 2
        test = new Node(1);
        addChildren(root, test, null);
    }  
        
    void makeCustomTree3(){    
        //Test Case: 3
        root = new Node(4);
        addChildren(root, new Node(2), new Node(5));
        test = new Node(3);
        addChildren(root.left, null, test);
    }   
     
    void makeCustomTree4(){ 
        //Test Case: 4
        root = new Node(2);
        test = root;
        addChildren(root, null, new Node(7)); 
    }
    
    void addChildren(Node parent, Node left, Node right){
        parent.left = left;
        parent.right = right;
        if(left!=null) left.parent = parent;
        if(right!=null) right.parent = parent;
    }
    
    public static void main(String[] args){
        Code tree = new Code();
        tree.makeCustomTree1();
        System.out.println(tree.getInorderSuccessor(tree.test));
        
        tree.makeCustomTree2();
        System.out.println(tree.getInorderSuccessor(tree.test));
        
        tree.makeCustomTree3();
        System.out.println(tree.getInorderSuccessor(tree.test));
        
        tree.makeCustomTree4();
        System.out.println(tree.getInorderSuccessor(tree.test));
    }
}

Output:

null
Value: 2
Value: 4
Value: 7

Monday, December 29, 2014

Checking if a given Binary Tree is a Binary Search Tree [Top-Down and Bottom-Up (Recursive) Approaches]

Q. Implement a function to check if a binary tree is a binary search tree.

Source:

public class Code{
    
    public class Node{
        int value;
        Node left, right;
        Node(){}
        Node(int value){this.value = value;}
        Node(int value, Node left, Node right){
            this.value = value;
            this.left = left;
            this.right = right;
        }
        
        @Override
        public String toString(){
            return "Value: "+value;
        }
    }
    
    Node root; 
    
    Integer previous = null;
    boolean isBSTMethod1(Node node){
       if(node == null)return true;
       if(!isBSTMethod1(node.left))return false;
       if(previous!=null && previous > node.value)return false;
       previous = node.value;
       return isBSTMethod1(node.right);
    }
    
    //Top down check
    boolean isBSTMethod2(Node node, Integer min, Integer max){
       if(node == null) return true;
       if((max != null && node.value >= max) || 
          (min != null && node.value < min)) return false;
       if(!isBSTMethod2(node.left, min, node.value)) return false;
       return isBSTMethod2(node.right, node.value, max);
    }
    
    class Pair{
        Integer min, max; 
        Pair(Integer min, Integer max){
            this.min = min;
            this.max = max;
        }
    }
    
    //Bottom Up Check
    boolean isBSTMethod3test(){
        isBST = true;
        isBSTMethod3(root);
        return isBST;
    }
    
    boolean isBST;
    Pair isBSTMethod3(Node node){ 
        if(node.left == null && node.right == null) return new Pair(node.value, node.value);
         
        Pair left, right;
        
        if(node.left == null) left = new Pair(node.value, null);
        else left = isBSTMethod3(node.left);
        if(!isBST)return null;
        
        if(node.right == null) right = new Pair(null, node.value);
        else right = isBSTMethod3(node.right);
        if(!isBST)return null;
        
        if((left.max != null && left.max >= node.value) || (right.min != null && right.min<node.value))
            isBST = false;
        
        return new Pair(left.min, right.max); 
    }
    
    //Other functions
    void makeCustom(){
        //Tree 1 - Comment out others
        root = new Node(5);
        root.left = new Node(2);
        root.right = new Node(10);
        root.left.right = new Node(40);
        root.left.left = new Node(1); 
        root.left.right.left = new Node(3);
        root.right.left = new Node(7);
        root.right.right = new Node(10); 
        
        /*
            Failure case for Method1. This binary tree mush have values of 
            node.right >= node && node.left < node
        */
        
        /*
          root = new Node(4);
          root.left = new Node(5);
          root.right = new Node(5);
        */
        
        /*
          //Tree 2
          root = new Node(25);
          root.left = new Node(10);
          root.right = new Node(40);
          root.left.right = new Node(20);
          root.left.left = new Node(5); 
          root.left.left.left = new Node(3); 
        */
        
        //Tree 3 
        root = new Node(35);
        root.left = new Node(15);
        root.left.left = new Node(7);
        root.left.left.left = new Node(4);
        root.left.left.right = new Node(9);
        root.left.right = new Node(20);
        root.left.right.left = new Node(17);
        root.left.right.right = new Node(34);
        root.right = new Node(55);
        root.right.left = new Node(40);
        root.right.left.left = new Node(37);
        root.right.left.right = new Node(50);
        root.right.right = new Node(60);
        root.right.right.left = new Node(57);
        root.right.right.right = new Node(65);
       
    }
    
    void printTree(String string){
        System.out.println(string);
        inorder(root);
    }
    
    void inorder(Node node){
        if(node==null)return;
        inorder(node.left);
        System.out.println(node.value);
        inorder(node.right);
    }
    
    public static void main(String[] args){
        Code tree = new Code();
        tree.makeCustom();
        System.out.println("Is this tree a BST? : "+tree.isBSTMethod2(tree.root, null, null));
        System.out.println("Is this tree a BST? : "+tree.isBSTMethod3test());
    }
}

Output:

Is this tree a BST? : true
Is this tree a BST? : true

Sunday, December 28, 2014

Creating a seperate LinkedList for all the nodes at each depth of a given binary tree

Q. Given a binary tree, design an algorithm which creates a linked list of all the nodes at each depth (e.g., if you have a tree with depth D, you'll have D linked lists).

Algorithm:

We can do this using Depth First Traversal or Breadth First Traversal

Source:

import java.util.Queue;
import java.util.ArrayList;
import java.util.LinkedList;

public class Code{
    
    public class Node{
        int value;
        Node left, right;
        Node(){}
        Node(int value){this.value = value;}
        Node(int value, Node left, Node right){
            this.value = value;
            this.left = left;
            this.right = right;
        }
        
        @Override
        public String toString(){
            return "Value: "+value;
        }
    }
    
    Node root; 
    
        //Using recursive DFS
    ArrayList<LinkedList<Node>> getNodesAtDepthsDFS(){
        ArrayList<LinkedList<Node>> list = new ArrayList<>();
        makeListDFS(root, list);
        return list;
    }
    
    int makeListDFS(Node node, ArrayList<LinkedList<Node>> r){
        if(node == null) return 0;
        int left = makeListDFS(node.left, r)+1; 
        int right = makeListDFS(node.right, r)+1;   
        int height = Math.max(left, right);
        LinkedList<Node> ll; 
        if(height == r.size()+1){
            ll = new LinkedList<>();
            r.add(ll);
        }else
            ll = r.get(height-1);
        ll.add(node);
        return height;
    }
    
    //Using iterative BFS 
    
    //BFS using a queue
    ArrayList<LinkedList<Node>> getNodesAtDepthsBFS(){ 
        ArrayList<LinkedList<Node>> r = new ArrayList<>();
        if(root==null)return r;
        Node t = root;
        Queue<Node> q = new LinkedList<>();
        q.add(t);
        int nextDepthAfter = 1 /*after 1 element has been dequeued */, depth = 0,
            dequeued = 0; /*dequeued so far*/
        while(!q.isEmpty()){    
            t = q.poll(); dequeued++;  
            LinkedList<Node> ll;
            if(depth == r.size()){
                ll = new LinkedList<>();
                r.add(ll);
            }else ll = r.get(depth); 
            ll.add(t);
            if(t.left!=null){q.add(t.left);}
            if(t.right!=null){q.add(t.right);}
            if(nextDepthAfter == dequeued){ depth++; nextDepthAfter = q.size(); dequeued=0;}
        }
        return r;
    } 
    
    //Straightforward BFS
    ArrayList<LinkedList<Node>> getNodesAtDepthsBFS2(){
        ArrayList<LinkedList<Node>> r = new ArrayList<>();
        if(root==null)return r;
        Node t = root;
        LinkedList<Node> parents = new LinkedList<>();
        parents.add(t); 
        
        while(!parents.isEmpty()){
            LinkedList<Node> temp = parents; 
            r.add(parents);
            parents = new LinkedList<>();
            for(Node child:temp){
                 if(child.left!=null)parents.add(child.left);
                 if(child.right!=null)parents.add(child.right); 
            } 
        }
        return r; 
    }
    
    //Other functions
    void makeCustom(){
        root = new Node(1);
        root.left = new Node(2);
        root.right = new Node(3);
        root.left.right = new Node(4);
        root.right.left = new Node(5);
        root.right.left.right = new Node(6);
    }
    
    void printTree(String string){
        System.out.println(string);
        inorder(root);
    }
    
    void inorder(Node node){
        if(node==null)return;
        inorder(node.left);
        System.out.println(node.value);
        inorder(node.right);
    }
    
    //Test
    public static void main(String[] args){ 
        Code tree = new Code();
         
        //DFS
        tree.makeCustom();
        tree.printTree("Printing tree contents"); 
        
        System.out.println("\nUsing DFS");
        ArrayList<LinkedList<Node>> r = tree.getNodesAtDepthsBFS(); 
        for(int i=0;i<r.size();++i) System.out.println("Depth = "+i+" Node: "+r.get(i)); 
        
        //BFS Using a queue
        System.out.println("\nBFS using a queue");
        r = tree.getNodesAtDepthsBFS(); 
        for(int i=0;i<r.size();++i) System.out.println("Depth = "+i+" Node: "+r.get(i));  
        
        //BFS - StraightForward method
        System.out.println("\nBFS - Method 2");
        r = tree.getNodesAtDepthsBFS2();
        for(int i=0;i<r.size();++i) System.out.println("Depth = "+i+" Node: "+r.get(i)); 
    }
}

Output:

Printing tree contents
2
4
1
5
6
3

Using DFS
Depth = 0 Node: [Value: 1]
Depth = 1 Node: [Value: 2, Value: 3]
Depth = 2 Node: [Value: 4, Value: 5]
Depth = 3 Node: [Value: 6]

BFS using a queue
Depth = 0 Node: [Value: 1]
Depth = 1 Node: [Value: 2, Value: 3]
Depth = 2 Node: [Value: 4, Value: 5]
Depth = 3 Node: [Value: 6]

BFS - Method 2
Depth = 0 Node: [Value: 1]
Depth = 1 Node: [Value: 2, Value: 3]
Depth = 2 Node: [Value: 4, Value: 5]
Depth = 3 Node: [Value: 6]

Constructing a minimum height BST with elements from a sorted array.

Q. Given a sorted (increasing order) array with unique integer elements, write an algorithm to create a binary search tree with minimal height.

Algorithm:

1. Pass the array reference, starting index (s) and end index (e) recursively.
2. Calculate mid = (e+s)/2
3. Construct a new Node with array[mid] as the value.
4. Now node.left = (array, s, mid-1)
5. node.right = (array, mid+1, e)
6. Return this node.
7. Returning condition during recursion:
  if(s > e) we must return null (no element to be placed there)
  if(s==e) return new Node(array[s])

Source:


public class Code{
    
    public class Node{
        int value;
        Node left, right;
        Node(){}
        Node(int value){this.value = value;}
        Node(int value, Node left, Node right){
            this.value = value;
            this.left = left;
            this.right = right;
        }
    }
    
    Node root;
    
    void construct(int[] a){
        root = build(a, 0, a.length-1);
    }
    
    Node build(int[] a, int s, int e){
        if(s>e)return null;
        else if(s==e)return new Node(a[s]);
        else{
            int mid = (e+s)/2;
            Node node = new Node(a[mid]);
            node.left = build(a, s, mid-1);
            node.right = build(a, mid+1, e);
            return node;
        }
    }
    
    void printTree(){
        inorder(root);
        System.out.println("Balanced? : "+isBalanced()+" Height = "+checkB(root));
    }
    
    void inorder(Node node){
        if(node==null)return;
        inorder(node.left);
        System.out.println(node.value);
        inorder(node.right);
    }
    
    boolean isBalanced(){
        return checkB(root)!=-1;
    }
    
    int checkB(Node node){
        if(node == null)return 0;
        int left = checkB(node.left)+1; if(left == 0)return -1;
        int right = checkB(node.right)+1; if(right == 0)return -1;
        int diff = Math.abs(left - right); if(diff > 1)return -1;
        else return Math.max(left, right);
    }
    
    int height(Node node){
        if(node == null)return 0;
        int left = checkB(node.left)+1; if(left == 0)return -1;
        int right = checkB(node.right)+1; if(right == 0)return -1; 
        return Math.max(left, right);
    }
    
    public static void main(String[] args){ 
        Code tree = new Code();
        int a[] = {3,4,2,1}; 
        tree.construct(a);
        tree.printTree();
    }
}

Output:

3
4
2
1
Balanced? : true Height = 3

A function to check if a binary tree is balanced.

Q. Implement a function to check if a binary tree is balanced. For the purposes of this question, a balanced tree is defined to be a tree such that the heights of the two sub trees of any node never differ by more than one.

Algorithm:

1. Go to the left in tree.
2. If a null is encountered, return 0.
3. Returned value is incremented (this is representing the height at that level).
4. Recursively go to the right in sub trees.
5. Return height from right sub tree.
6. If difference between heights is between [-1 to 1] then return the max of heights of left and right else return -1(unacceptable height) and stop further evaluation. (Since if a sub tree is unbalanced, so it the whole tree).

Source:

class Tree{
     
    class Node{
        int value;
        Node left, right;
        Node(){}
        Node(int value){this.value = value;}
        Node(int value, Node left, Node right){
            this.value = value;
            this.left = left;
            this.right = right;
        }
    }

    Node root;
    
    void buildTree(){
        root = new Node(3);
        root.right = new Node(2);
        root.left = new Node(1);
        Node l = root.left;
        l.left = new Node(4);
        l.right = new Node(5);
        l.right.right = new Node(1772);
        l.right.left = new Node(89);
        
        root.right.left = new Node(88);
    }
    
    boolean checkBalanced(){
        return checkB(root)!=-1;
    }
    
    int checkB(Node node){
        if(node == null)return 0;
        int left = checkB(node.left)+1; if(left == 0)return -1;
        int right = checkB(node.right)+1; if(right == 0)return -1;
        int diff = Math.abs(left - right); if(diff > 1)return -1;
        else return Math.max(left, right);
    }
    
    public static void main(String[] args){
        Tree t = new Tree();
        t.buildTree();
        System.out.println(t.checkBalanced());
    }
}

Output:

true

Sorting a given stack using one additional stack.

Q. Write a program to sort a stack in ascending order (with biggest items on top). You may use at most one additional stack to hold items, but you may not copy the elements into any other data structure (such as an array). The stack supports the following operations: push, pop, peek and isEmpty.


Algorithm:

1. We will have two stacks, first one is the given unsorted one and the second one will be sorted which will be returned by the method call.
2. Pop an item from first stack and push it to the second.
3. Pop an item from the unsorted (first) stack (storing it in a temp variable) and compare it with sorted array's head. If head is larger, pop it and push it to unsorted stack. Do this until the value at head is < or = to the temp element.
4. At the time when the loop stops, the value below is less than or equal to temp variable, we can now push it to the sorted stack.
5. Now push back all the items that were originally in stack 2 and were shifted to stack 1 to accommodate the temp item.
6. Do this until stack 1 becomes empty.
7. Stack 2 contains the sorted data and can now be returned.

Source:

class OrderedStack<T extends Comparable<T>> extends Stack<T>{ 
    public OrderedStack(int size) {
        super(0); 
        elements = (T[])new Comparable[size];  
    } 
}

class StackSorter{
    
    public static <T extends Comparable<T>> OrderedStack<T> sort(Stack<T> unsorted){
        OrderedStack<T> sorted = new OrderedStack<>(unsorted.size());
        if(unsorted.isEmpty())return sorted;
        
        sorted.push(unsorted.pop());
        while(!unsorted.isEmpty()){
            T temp = unsorted.pop(); 
            int i=0; 
            while(!sorted.isEmpty() && sorted.peek().compareTo(temp)>0){
                unsorted.push(sorted.pop());i++;
            }
            sorted.push(temp);
            while(i--!=0)sorted.push(unsorted.pop());
        }
        return sorted;
    } 
}

public class Code{
    public static void main(String[] args){
        Integer test[] = {2,3,4,4,2,22,34,5,6,7,8,867,1,5};
        Stack<Integer> stack = new Stack<>(test.length);

        for(int i:test)stack.push(i);
        stack = StackSorter.sort(stack);
        while(!stack.isEmpty())System.out.print(stack.pop()+ " ");
    }
}


public class Stack <T>{
    int top = -1; 
    T[] elements;
    
    public Stack(int size){  
        elements = (T[])new Object[size];  
    }
    
    public int size(){ 
        return top+1;
    }
    
    public void push(T element){ 
        if(top+1 == elements.length){
            System.out.println("Overflow.");
            return;
        }
        elements[++top] = element;
    }
    
    public T pop(){
        if(top<0){
            System.out.println("Underflow.");
            return null;
        }
        return elements[top--];
    }
        
    public T peek(){
        if(top < 0){
            System.out.println("Stack is empty!");
            return null;
        }
        return elements[top];
    }
    
    public boolean isEmpty(){
        return top==-1;
    } 
}

Output:

867 34 22 8 7 6 5 5 4 4 3 2 2 1

Implementing a queue using two stacks.

Q. Implement a MyQueue class which implements a queue using two stacks.

Algorithm:

1. There are two stacks stack1, stack2.
2. Suppose we are adding elements 1,3,4,5,2.
3. For adding them to the queue, we push them to stack 1.
4. For finding the min, we pop all of them to stack 2 and then pop form stack 2.
5. As long as there are elements in stack 2, finding min is easy, just pop from stack 2.
6. If stack 2 is empty and we need to find min, pop again all elements from stack 1 to stack 2 and pop from stack 2.

Source:

public class MyQueue<T>{
    Stack<T> stack1, stack2;
    int max;
    
    MyQueue(int size){
        max = size;
        stack1 = new Stack<>(size);
        stack2 = new Stack<>(size);
    }
    
    public int size(){
        return stack1.size() + stack2.size();
    }
    
    public void enqueue(T val){
        if(stack1.size() == max){
            if(stack2.isEmpty())shiftto2();
            else return;
        }
        stack1.push(val);
    }
    
    public T dequeue(){
        if(size() == 0)return null;
        if(stack2.isEmpty())shiftto2(); 
        return stack2.pop(); 
    }
    
    private void shiftto2(){
        while(!stack1.isEmpty())
            stack2.push(stack1.pop());
    }
    
    public T peek(){
        if(size() == 0)return null;
        if(stack2.isEmpty())shiftto2();
        return stack2.peek(); 
    } 
}

public class Code{
    public static void main(String[] args){
        MyQueue<Integer> mq = new MyQueue<>(5);
        for(int i=0;i<9;++i)mq.enqueue(i);
        System.out.println(mq.dequeue());
        for(int i=3;i<8;++i)mq.enqueue(i);
        for(int i=0;i<9;++i)System.out.println(mq.dequeue());
    }
}

Stack Class

public class Stack <T>{
    int top = -1; 
    T[] elements;
    
    public Stack(int size){  
        elements = (T[])new Object[size];  
    }
    
    public int size(){ 
        return top+1;
    }
    
    public void push(T element){ 
        if(top+1 == elements.length){
            System.out.println("Overflow.");
            return;
        }
        elements[++top] = element;
    }
    
    public T pop(){
        if(top<0){
            System.out.println("Underflow.");
            return null;
        }
        return elements[top--];
    }
        
    public T peek(){
        if(top < 0){
            System.out.println("Stack is empty!");
            return null;
        }
        return elements[top];
    }
    
    public boolean isEmpty(){
        return top==-1;
    } 
} 

Output:

0
1
2
3
4
5
6
7
8
3

Saturday, December 27, 2014

Solve Towers of Hanoi problem using stacks to move disks from the first tower to last tower.

Q. In the classic problem of the Towers of Hanoi, you have 3 towers and N disks of different sizes which can slide onto any tower. The puzzle starts with disks sorted in ascending order of size form top to bottom (i.e., each disk sites on top of an even larger one). You have the following constraints:

1. Only one disk can be moved at a time.
2. A disk is slid off the top of one tower onto the next tower.
3. A disk can only be placed on top of a larger disk.

Write program to move the disks from the first tower to the last using stacks.

Algorithm (For Towers of Hanoi: http://www.codebytes.in/2014/09/towers-of-hanoi-recursive-solution.html )

Source:

import java.lang.reflect.Array;

class Tower{
    Stack<Integer> disks;

    Tower(int ndisks){
        disks = new Stack<>(ndisks);
    }
}

class TOH{ 
    int n;
    Tower[] towers;
    
    TOH(int disks, int sourceTower){ 
        n = disks;
        towers = (Tower[])Array.newInstance(Tower.class, 3);
        for(int i=0;i<towers.length;++i)towers[i] = new Tower(n);
        for(int i=disks;i>=1;--i)towers[sourceTower].disks.push(i);
    }
    
    void move(int disks, Tower source, Tower destination, Tower buffer){
        if(disks==1)destination.disks.push(source.disks.pop());
        else{
            move(disks-1, source, buffer, destination); 
            destination.disks.push(source.disks.pop());
            move(disks-1, buffer, destination, source);
        }
    }
    
    void move(int source, int buffer, int destination){
        if(towers[source].disks.isEmpty())System.out.println("Tower is empty!");
        else move(n, towers[source], towers[destination], towers[buffer]);
    }
}

public class Code{
    public static void main(String[] args){
        TOH toh = new TOH(4, 0);
        toh.move(0, 1, 2);
        while(!toh.towers[2].disks.isEmpty()){
            System.out.println(toh.towers[2].disks.pop());
        }
    }
}

Stack Class

public class Stack <T>{
    int top = -1; 
    T[] elements;
    
    public Stack(int size){  
        elements = (T[])new Object[size];  
    }
    
    public int size(){ 
        return top+1;
    }
    
    public void push(T element){ 
        if(top+1 == elements.length){
            System.out.println("Overflow.");
            return;
        }
        elements[++top] = element;
    }
    
    public T pop(){
        if(top<0){
            System.out.println("Underflow.");
            return null;
        }
        return elements[top--];
    }
        
    public T peek(){
        if(top < 0){
            System.out.println("Stack is empty!");
            return null;
        }
        return elements[top];
    }
    
    public boolean isEmpty(){
        return top==-1;
    } 
}

Output:

1
2
3
4