285. Inorder Successor in BST
- Total Accepted: 17302
- Total Submissions: 47674
- Difficulty: Medium
- Contributors: Admin
Given a binary search tree and a node in it, find the in-order successor of that node in the BST.
Note: If the given node has no in-order successor in the tree, return null.
Code
# Definition for a binary tree node.
# class TreeNode(object):
# def __init__(self, x):
# self.val = x
# self.left = None
# self.right = None
class Solution(object):
def inorderSuccessor(self, root, p):
"""
:type root: TreeNode
:type p: TreeNode
:rtype: TreeNode
"""
if (not p) or (not root):
return None
# if p has right child, its inorder successor is
# the leftmost leaf of his right child
if p.right:
return self.leftmost(p.right)
# record the most recent traversed node that has the left branch leading to p
prev_root = None
while root != p:
if p.val <= root.val:
prev_root = root
root = root.left
else:
root = root.right
return prev_root
def leftmost(self, node):
while node.left:
node = node.left
return node
Idea
If p has right child, then its inorder successor is the leftmost leaf of his right child
Otherwise, p’s inorder successor is the most recent traversed node that has the left branch leading to p.
Actually, the code can be simplified as:
# Definition for a binary tree node.
# class TreeNode(object):
# def __init__(self, x):
# self.val = x
# self.left = None
# self.right = None
class Solution(object):
def inorderSuccessor(self, root, p):
"""
:type root: TreeNode
:type p: TreeNode
:rtype: TreeNode
"""
succ = None
while root:
# think in this way: find the smallest element
# that is larger than p
if p.val < root.val:
succ = root
root = root.left
else:
root = root.right
return succ
Reference: https://discuss.leetcode.com/topic/25698/java-python-solution-o-h-time-and-o-1-space-iterative