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

No comments:

Post a Comment