aero2146

Inorder Successor in BST

Apr 10th, 2020
172
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
  1. class Solution:
  2.     def inorderSuccessor(self, root: 'TreeNode', p: 'TreeNode') -> 'TreeNode':
  3.         # the successor is somewhere lower in the right subtree
  4.         # successor: one step right and then left till you can
  5.         if p.right:
  6.             p = p.right
  7.             while p.left:
  8.                 p = p.left
  9.             return p
  10.        
  11.         # the successor is somewhere upper in the tree
  12.         stack, inorder = [], float('-inf')
  13.        
  14.         # inorder traversal : left -> node -> right
  15.         while stack or root:
  16.             # 1. go left till you can
  17.             while root:
  18.                 stack.append(root)
  19.                 root = root.left
  20.                
  21.             # 2. all logic around the node
  22.             root = stack.pop()
  23.             if inorder == p.val:    # if the previous node was equal to p
  24.                 return root         # then the current node is its successor
  25.             inorder = root.val
  26.            
  27.             # 3. go one step right
  28.             root = root.right
  29.  
  30.         # there is no successor
  31.         return None
RAW Paste Data