Published: Sep 30, 2022
If the tree is the binary search tree (BST), the inorder successor has next bigger value. Basic idea is the same as the binary tree inorder traversal. However, using BST’s property, we can go to one of left or right subtree instead of both.
rootof a binary search tree and a node p in it, return the in-order successor of that node in the BST. If the given node has no in-order successor in the tree, return null.
The successor of a node
pis the node with the smallest key greater than
- The number of nodes in the tree is in the range
-10**5 <= Node.val <= 10**5
- All Nodes will have unique values.
Example 1 Input: root = [2,1,3], p = 1 Output: 2 Explanation: 2 / \ 1 3 1's in-order successor node is 2. Note that both p and the return value is of TreeNode type.
Example 2 Input: root = [5,3,6,2,4,null,null,1], p = 6 Output: null Explanation: 5 / \ 3 6 / \ 2 4 / 1 There is no in-order successor of the current node, so the answer is null.
Since the tree is BST, compare the value to go which subtree. If the root node’s value is greater than the given node, go left. Otherwise, go right. The successor is the smallest in the right subtree or parent if the node is a left child. If the node is a right child and doesn’t have the right subtree, no successor exists.
# Definition for a binary tree node. # class TreeNode: # def __init__(self, x): # self.val = x # self.left = None # self.right = None class InorderSuccessorInBST: def inorderSuccessor(self, root: TreeNode, p: TreeNode) -> Optional[TreeNode]: if not root or not p: return None if root.val > p.val: return self.inorderSuccessor(root.left, p) or root return self.inorderSuccessor(root.right, p)
O(n)– worst case. if bst is balanced, it will be O(log(n))