Inorder Successor in BST

Given a binary search tree (BST) and a specific node p, you are required to find the in-order successor of that node in the BST. The in-order successor is the node with the smallest key greater than p.val. If there’s no successor, return null.

Approach

1. Iterative In-order Traversal: Start by performing an in-order traversal of the tree. During the traversal, you will keep track of the previous node, looking for the node that matches p. When p is found, the next node in the traversal order is its in-order successor.

2. 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 in-order 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 in-order successor.

Here’s a code snippet implementing the second approach:

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12

class Solution:
    def inorderSuccessor(self, root: TreeNode, p: TreeNode) -> Optional[TreeNode]:
        successor = None

        while root:
            if p.val < root.val:
                successor = root
                root = root.left
            else:
                root = root.right

        return successor

Explanation

• If p has a right subtree, its in-order 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 of p is smaller than the current node’s value. Keep track of the last node where a left turn was made. That node is the in-order successor.
• If no such node is found, return None.

Key Takeaways

• This solution leverages the properties of a BST to find the in-order 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)

1. Inorder successor

2. Can we have duplicates in a BST?

3. Define the interface Input: TreeNode instance root and p Output: TreeNode instance of the inorder successor

4. Bruteforce force [1,2,3]

   • Doing work than necessary
   • Array is used to store
   • T/S similar complexity

5. 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 : left-Root-right 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

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26

# Definition for a binary tree node.
# class TreeNode
#     attr_accessor :val, :left, :right
#     def initialize(val)
#         @val = val
#         @left, @right = nil, nil
#     end
# end

# @param {TreeNode} root
# @param {TreeNode} p
# @return {TreeNode}

def inorder_successor(root, p)
    parent = nil

    while root
       if p.val < root.val
           parent = root
           root = root.left
       else
          root = root.right 
       end
    end
    return parent
end