510. Inorder Successor in BST II

Given a node in a binary search tree, return the in-order successor of that node in the BST. If that node has no in-order successor, return null.

The successor of a node is the node with the smallest key greater than node.val.

You will have direct access to the node but not to the root of the tree. Each node will have a reference to its parent node. Below is the definition for Node:

class Node {
   public int val;
   public Node left;
   public Node right;
   public Node parent;
}

/*
// Definition for a Node.
class Node {
public:
    int val;
    Node* left;
    Node* right;
    Node* parent;
};
*/

class Solution {
    Node* findRightChild(Node* node, int val) {
        while(node->left and node->left->val > val)
            node = node->left;
        return node;
    }
    Node* findParentRightChild(Node* node, int val) {
        while(node) {
            if(node->val > val) return node;
            if(node->right and node->right->val > val)
                return findRightChild(node->right, val);
            node = node->parent;
        }
        return node;
    }
public:
    Node* inorderSuccessor(Node* node) {
        if(node->right != NULL) return findRightChild(node->right, node->val);
        if(node->parent != NULL) return findParentRightChild(node->parent, node->val);
    
        return NULL;
    }
};