BinaryTreeFindNext_noParentPointer, Java

BinaryTreeFindNext_noParentPointer

//Title of this code
//'main' method must be in a class 'Rextester'.
//Compiler version 1.7.0_51

import java.util.*;
import java.lang.*;

class Rextester
{  
    public static void main(String args[])
    {
        TreeNode root=new TreeNode(10);
		TreeNode n2=new TreeNode(1);
		TreeNode n3=new TreeNode(7);
		TreeNode n4=new TreeNode(4);
		TreeNode n5=new TreeNode(9);
		TreeNode n0=new TreeNode(12);
		TreeNode n6=new TreeNode(15);
		TreeNode n7=new TreeNode(20);
		root.left=n4;
		root.right=n6;
		n4.left=n2;
		n4.right=n3;
		n3.right=n5;
		n6.left=n0;
		n6.right=n7;
        System.out.println(findNext(root, root).val);
        return;
    }
    static class TreeNode{
        int val;
        TreeNode left;
        TreeNode right;
        TreeNode(){};
        TreeNode(int v){
            val=v;
        }
    }
    private static TreeNode findParent(TreeNode root, TreeNode node)
    {
        TreeNode par=null;
        TreeNode cur=root;
        while (cur!=null&&cur.val!=node.val)
        {
            if (cur.val>node.val)
            {
                par=cur;
                cur=cur.left;
            }
            else
            {
                par=cur;
                cur=cur.right;
            }
        }
        return par;        
    }
    private static TreeNode findNext(TreeNode root, TreeNode node)
    {
        TreeNode res=new TreeNode(-1);
        //Corner case: no object
        if (root==null)
        {
            return res;
        }
        //search for the node and its parent
        TreeNode cur=root;
        TreeNode par=new TreeNode(-1);
        while (cur!=null&&cur.val!=node.val)
        {
            par=cur;
            if (cur.val>node.val)
            {
                cur=cur.left;
            }
            else
            {
                cur=cur.right;
            }
        }
        if (cur==null)
            return res;
        //if the node has right child
        if (cur.right!=null)
        {
            res=findMin(cur.right);
        }
        //if not, find in the parent
        else if (cur==par.right)
        {
            while (par!=null&&cur==par.right)
            {
                cur=par;
                par=findParent(root,cur);
            }
            if (par==null)
                return res;
            else{
                res=par;
            }            
        }
        else
        {
            res=par;
        }
        return res;       
        
    }
    private static TreeNode findMin(TreeNode root)
    {
        TreeNode node=root;
        while (node.left!=null)
        {
            node=node.left;
        }
        return node;
    }
}


run \| edit \| history \| help	0