﻿

# 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