package org.santhoshkumar.Trees;

/**
 * Created by sk010962 on 10/20/2015.
 */
public class InorderSuccessor {
    Node root;

    public Node getSucessor(Node node){

        // If node has right child then get the leftmost node of the right subtree
        if (node.right != null){
            return getLeftMost(node.right);
        }
        // If right subtree is null then get the successor will be one of the ancestor node

        // If node is the last right child then sucessor is null
        return null;
    }

    public Node getLeftMost(Node node){
        if(node.left == null){
            return node;
        }
        Node current = node;
        while(current.left != null){
            current = current.left;
        }
        return current;
    }

    public Node getAncestor(Node root, Node node){
        return null;
    }

    //Using parent link
    public Node getInOrderSuccessor(Node node){
        if(node.right != null){
            Node current = node.right;
            while(current.left != null){
                current = current.left;
            }
            return current;
        }else{
            while(node.parent != null && node == node.parent.right){
                node = node.parent;
            }
            return node.parent;
        }
    }
}

@@ -143,16 +143,17 @@
 e getSuc
+c
 essor(No
@@ -162,16 +162,16 @@
  node)%7B%0A
-
 %0A       
@@ -425,16 +425,54 @@
 or node%0A
+        return getAncestor(root,node);
 %0A       
@@ -515,16 +515,17 @@
 then suc
+c
 essor is
@@ -530,37 +530,16 @@
 is null%0A
-        return null;%0A
     %7D%0A%0A 
@@ -829,32 +829,422 @@
 ot, Node node)%7B%0A
+        if(root==null) %7B%0A            return null;%0A        %7D%0A        Node successor = null;%0A        if(root== node%7C%7C(successor = getAncestor(root.left, node))!=null%7C%7C(successor=getAncestor(root.right,node))!=null)%7B%0A%0A            if(successor!=null)%7B%0A                if(root.left==successor)%7B%0A                    return root;%0A                %7D%0A            %7D%0A            return root;%0A        %7D%0A
         return n
@@ -1255,22 +1255,23 @@
 %0A    %7D%0A%0A
-
     //
+ 
 Using pa

In order successor