285.Inorder Successor in BST

Tags: [inorder], [inorder_traversal], [tree], [binary_tree], [iteration], [successor], [BST], [binary_search_tree], [binary_search]

Com: {fb}

Link: https://leetcode.com/problems/inorder-successor-in-bst/\#/description

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.

Solution: Inorder Traversal Iteration

# 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 root or not p:
            return None

        prev = None
        curr = root
        stack = []

        while curr or stack:
            if curr:
                stack.append(curr)
                curr = curr.left
            else:
                curr = stack.pop()
                if p == prev:
                    return curr

                prev = curr
                curr = curr.right

        return None

Revelation:

• Inorder traversal: try your best to go to left, once you can not go to left, go to right one step, then try left again.
• I think there is another approach to solve this problem: Because this is BST, we can first get the entire inorder traversal sequence, which should be a sorted string, then we do binary search to find the index of the p, then the next element will be the successor we want to find. The time complexity is also O(n), but it will waste some space.

Note:

• Time complexity = O(n), n is the number of nodes of the given tree.