Preorder Successor of a Node in Binary Tree

https://www.geeksforgeeks.org/preorder-successor-node-binary-tree/

Given a binary tree and a node in the binary tree, find preorder successor of the given node.

Examples: Consider the following binary tree
              20            
           /      \         
          10       26       
         /  \     /   \     
       4     18  24    27   
            /  \
           14   19
          /  \
         13  15
Input :  4
Output : 10
Preorder traversal of given tree is 20, 10, 4, 
18, 14, 13, 15, 19, 26, 24, 27.

Input :  19
Output : 15

A simple solution is to first store Preorder traversal of the given tree in an array then linearly search given node and print node next to it.

Time Complexity : O(n)
Auxiliary Space : O(n)

An efficient solution is based on below observations.

1. If left child of given node exists, then the left child is preorder successor.
2. If left child does not exist and given node is left child of its parent, then its sibling is its preorder successor.
3. If none of above conditions are satisfied (left child does not exist and given node is not left child of its parent), then we move up using parent pointers until one of the following happens.
   • We reach root. In this case, preorder successor does not exist.
   • Current node (one of the ancestors of given node) is left child of its parent, in this case preorder successor is sibling of current node.

- code is flawed
Node* preorderSuccessor(Node* root, Node* n)

{

    // If left child exists, then it is preorder

    // successor.

    if (n->left)

        return n->left;

    // If left child does not exist, then

    // travel up (using parent pointers)

    // until we reach a node which is left

    // child of its parent.

    Node *curr = n, *parent = curr->parent;

    while (parent != NULL && parent->right == curr) {

        curr = curr->parent;

        parent = parent->parent;

    }

    // If we reached root, then the given

    // node has no preorder successor

    if (parent == NULL)

        return NULL;

    return parent->right;

}

https://algorithmsgeek.blogspot.com/2013/06/algo6-preorder-successor-in-binary-tree.html

Following is simple algorithm for finding Preorder Successor of binary tree.

Step 1: Current root itself is NULL, then successor is also NULL.

Step 2: Current root contains value same as key for which we are looking successor.

        2.1: Current root has right child, then left most node of right child is successor.

        2.2: Current root does have right child r, then r is successor.
        2.3: Current root is left leaf node and having sibling on right side

        2.4: Otherwise, if current root has an ancestor, v, which is a left-child and v has a right sibling, vrs, then succ(current root) is vrs
        2.5: If none of above applies, then succ(current root) doesn't exist.

Step 3: Current root is not the target node for which we are looking successor.

        3.1: Search target node and its successor in left side of tree recursively, and return if found.

        3.2: Search target node and its successor in right side of tree recursively, and return.