Inorder Successor in BST

Given a binary search tree and a node in it, find the in-order successor of that node in the BST.

Note: If the given node has no in-order successor in the tree, return null.

Solution

/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode(int x) { val = x; }
 * }
 */
public class Solution {
 public TreeNode inorderSuccessor(TreeNode root, TreeNode p) {
        if (p == null) return null;

        if (p.right != null) {

            TreeNode runner = p.right;
            while (runner.left != null) {
                runner = runner.left;
            }

            return runner;

        } else {

            Map<TreeNode, TreeNode> map = new HashMap<>();
            boolean exist = search(root, p, map);
            if (!exist) {
                return null;
            } else {

                TreeNode parent = map.get(p);
                TreeNode runner = p;
                while (parent != null && parent.right != null && runner != null && parent.right.equals(runner)) {
                    runner = parent;
                    parent = map.get(runner);
                }

                return parent;
            }
        }

    }

    private boolean search(TreeNode root, TreeNode p, Map<TreeNode, TreeNode> map) {
        if (root == null) {
            return false;
        }

        if (root.equals(p)) {
            return true;
        }

        boolean leftFlag = false;
        if (root.left != null) {
            map.put(root.left, root);
            leftFlag = search(root.left, p, map);
        }

        boolean rightFlag = false;
        if (root.right != null) {
            map.put(root.right, root);
            rightFlag = search(root.right, p, map);
        }

        return leftFlag || rightFlag;
    }

}