Inorder Successor in BST
Given a binary search tree (BST) and a specific node p
, you are required to find the inorder successor of that node in the BST. The inorder successor is the node with the smallest key greater than p.val
. If there’s no successor, return null.
Approach
Iterative Inorder Traversal: Start by performing an inorder traversal of the tree. During the traversal, you will keep track of the previous node, looking for the node that matches
p
. Whenp
is found, the next node in the traversal order is its inorder successor.Using the Properties of BST: As a BST has the property that nodes to the left are smaller and nodes to the right are larger, you can use this property to find the successor more efficiently. If
p
has a right child, the leftmost node of the right subtree is the inorder successor. If not, traverse the tree from the root and keep track of the last node where you took a left turn. This node will be the inorder successor.
Here’s a code snippet implementing the second approach:


Explanation
 If
p
has a right subtree, its inorder successor is the leftmost node of that right subtree.  If
p
doesn’t have a right subtree, traverse from the root of the BST, taking the left turn as long as the value ofp
is smaller than the current node’s value. Keep track of the last node where a left turn was made. That node is the inorder successor.  If no such node is found, return
None
.
Key Takeaways
 This solution leverages the properties of a BST to find the inorder successor efficiently.
 The time complexity of this solution is (O(\log n)), where (n) is the number of nodes in the tree, provided the tree is balanced. In the worst case, if the tree is skewed, the time complexity will be (O(n)).
 The space complexity is (O(1)) since we only use constant extra space.
Traversal is inorder.
1,2,3 —> 2 comes after 1 (p = 1)
Inorder successor
Can we have duplicates in a BST?
Define the interface Input: TreeNode instance root and p Output: TreeNode instance of the inorder successor
Bruteforce force [1,2,3]
 Doing work than necessary
 Array is used to store
 T/S similar complexity
Leverage the BST property Search If smaller go to the left If greater go to the righ Pattern If you are a left node, your parent is the inorder successor p = 3, inorder = 4 Search for node with val 3
p=5, inorder = 6 Search for node with val 5 Inorder : leftRootright Cases a. Root is the same as p val b. p lies in the left subtree c. p lies in the right subtree
def inorderSuccessor(self, root, p): succ = None while root: if p.val < root.val: succ = root root = root.left else: root = root.right return succ

