285. Inorder Successor in BST

Problem Statement

link: LeetCode.cn LeetCode Given the root of 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 p is the node with the smallest key greater than p.val.

Example:

Input: root = [2,1,3], p = 1 Output: 2

Input: root = [5,3,6,2,4,null,null,1], p = 6 Output: null

Constraints: The number of nodes in the tree is in the range [1, 104]. -105 <= Node.val <= 105 All Nodes will have unique values.

Solution Approach

Recursive Method: Perform an in-order traversal, updating the successor when encountering a node with a value greater than the target node, and terminate early once the successor is found.

Iterative Method: Traverse the tree iteratively, updating the successor each time a node with a value greater than the target node is found, and continue until reaching a leaf node or finding the successor.

Complexity

Recursive Method Time Complexity: O(N) in the worst case, where N is the number of nodes in the tree, since the in-order traversal might visit every node. Space Complexity: O(H) where H is the height of the tree, due to the recursion stack. In the worst case, H could be O(N) for a skewed tree. Iterative Method Time Complexity: O(H) where H is the height of the tree, since the algorithm only needs to traverse down the tree from the root to a leaf node. Space Complexity: O(1) as it uses a constant amount of extra space aside from the input tree itself.

Algorithm

Recursive Method

In-Order Traversal: Perform an in-order traversal starting from the root, recursively exploring the left subtree, current node, and then the right subtree.

Check and Update Successor: During the traversal, if a node’s value is greater than the target node’s value and no successor has been found yet, update the successor to the current node and terminate the recursion.

Base Case: If the traversal reaches a null node or the successor is found, return immediately to stop further traversal.

Iterative Method

Tree Traversal: Begin at the root and iteratively move through the tree, deciding to traverse left or right based on the current node’s value relative to the target node’s value.

Update Successor: If the current node’s value is greater than the target node’s value, update the potential successor to this node and continue searching in the left subtree.

Termination: Continue the traversal until reaching a null node, and return the last updated potential successor, or null if no successor is found.

Implement

    # Definition for a binary tree node. # class TreeNode: #     def __init__(self, x): #         self.val = x #         self.left = None #         self.right = None
class Solution:
    def inorderSuccessor(self, root: TreeNode, p: TreeNode) -> Optional[TreeNode]:
        self.ans = None
        def dfs(root):
            if not root: return
            dfs(root.left)
            if not self.ans and root.val > p.val: 
                self.ans = root
                return
            dfs(root.right)
        dfs(root)
        return self.ans

    def inorderSuccessor(self, root: TreeNode, p: TreeNode) -> Optional[TreeNode]:
        ans = None
        while root:
            if root.val>p.val:
                ans = root
                root = root.left 
            else:
                root = root.right 
        return ans

    
    

Twitter  facebook  Email