how to find next Node in preOrder traverse recursively

Question

I want to write a function which takes a node of tree. It should return what is the next Node visited after the taken node in preOrder. I have written this Code: (This code searches for the left child and returns it. If the temp has no left child but it has right child this function returns right one. but if the Node is a leaf and has no child it gets parents until get a node that has right child.)

    public Node fineNextPreOrder(Node temp)
    {
    if(temp.left!=null)
        return temp.left;
    else if((temp.left==null)&&(temp.right!=null))
        return temp.right;
    else if((temp.left==null)&&(temp.right==null))
    {
        while((temp!=root)&&(!((temp.parent.left!=null)&&(temp.parent.left==temp)&&(temp.parent.right!=null))))
            temp = temp.parent;
        if(temp != root)
            return temp.parent.right;
    }

        return null;

}

It works true but I want to make it recursive.

can Any one please help me with this??

Thanks in advance for your Attention.

Answer 1

public Node preOrderMod(Node temp)
{
    if (temp != null)
    {
        if (temp.left != null)
            return temp.left;

        if (temp.right != null)
            return temp.right;

        return mod(temp.parent);
    }

    return null;
}

private Node mod(Node temp)
{
    if (temp != null && temp != root)
    {
       if (temp.parent.left == temp && temp.parent.right != null)
          return temp.parent.right;

       return mod(temp.parent);
    }

    return null;
}

For reference:

Pre-Order: root left right
In-Order: left root right
Post-Order: left right root