Ledger Nano X - The secure hardware wallet
SHARE
TWEET

Inorder Successor in BST

aero2146 Apr 10th, 2020 151 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
We use cookies for various purposes including analytics. By continuing to use Pastebin, you agree to our use of cookies as described in the Cookies Policy. OK, I Understand
Top