"""
# Definition for a Node.
class Node:
def __init__(self, val):
self.val = val
self.left = None
self.right = None
self.parent = None
"""
class Solution:
def inorderSuccessor(self, node: 'Node') -> 'Node':
"""
tc O(N) sc O(lgN)
main idea: first check if there is right child, find the left most of right node
if no right child node, find current node's parent's where its left node is current node, since the feature of BST, the smallest greater node is its parent
"""
# if there is right child, first choice right child
if node.right:
cur = node.right
while cur.left: # check if exist left child
cur = cur.left
return cur
else: # if there is no right child, left child is not considered.
# go check parent, if parent value is smaller than cur => cur is parent node's right tree => we need to go up all the way to find the first time current subtree is parent node's left subtree==> return parent node
cur = node.parent
while cur and cur.val < node.val:
cur = cur.parent
return cur