285. Inorder Successor in BST

Problem Description

The problem is set within the context of a binary search tree (BST), a type of binary tree where each node has the following properties:

• The left subtree of a node contains only nodes with keys less than the node's key.
• The right subtree of a node contains only nodes with keys greater than the node's key.
• Both the left and right subtrees must also be binary search trees.

Given such a tree and a particular node p in it, you need to find the "in-order successor" of that node. The in-order successor for a given node p in a BST is defined as the node with the smallest key that is greater than p.val. If such a node doesn't exist, in other words, if p is the node with the highest value in the tree, the function should return null.

The in-order traversal of a BST produces the node values in an ascending order. So the task could also be seen as finding the next node in the in-order traversal sequence.

Intuition

When trying to understand the solution, it's critical to grasp what it means by in-order traversal and how the properties of a binary search tree can streamline our search for the successor node.

The in-order traversal for a BST involves visiting the left subtree, then the node itself, and then the right subtree. When looking for the successor of node p, if p has a right subtree, then the successor would be the leftmost node in that right subtree. If p does not have a right subtree, the successor would be one of its ancestors, specifically the one for whom p is situated in the left subtree.

The proposed solution uses this understanding and traverses the tree starting from the root. At each step, it compares the current node's value to p.val to decide the direction of the search:

• If the current node's value is greater than p.val, the current node is a potential successor, and we go left to find a smaller one that is still larger than p.val.
• If the current node's value is less than or equal to p.val, the current node can't be the successor, and we go right to find a larger one.

The variable ans is used to keep track of the latest potential successor. This works because of the BST property: going left finds smaller keys and going right finds larger keys. When the algorithm finishes traversing the tree (root becomes None), the ans variable either contains the in-order successor node or remains None, meaning there is no successor (if p is the maximum element).

This algorithm ensures that we only travel down the tree once, providing an efficient solution with O(h) time complexity, where h is the height of the tree.

Learn more about Tree, Depth-First Search, Binary Search Tree and Binary Tree patterns.

Solution Approach

The implementation of the solution follows a straightforward approach utilizing the binary search tree properties to efficiently find the in-order successor.

Firstly, let's outline the core components of the algorithm:

• While Loop: The algorithm uses a loop to iterate through the nodes of the tree, starting at the root. The loop continues until root becomes None, which means we have reached the end of our search path in the BST.
• Conditional Checking: Inside the loop, a conditional check compares the current node's value (root.val) with the value of the node p (p.val). This comparison dictates the traversal direction because of the binary search tree arrangement.
• Potential Successor Update (ans): If the current node's value is greater than p.val, it means this node could potentially be the successor. We store this node to ans and continue searching to the left for a smaller value that would still be larger than p.val.
• Traversal Direction:
  • If root.val > p.val, we move left (root = root.left) in search of a smaller yet greater value than p.val.
  • If root.val <= p.val, we move right (root = root.right) since we know that all values in the left subtree are smaller and cannot be the successor.

The algorithm makes use of the BST property that left descendants are smaller and right descendants are larger than the node itself. Hence, we can discard half of the tree in each step of the while loop, similar to a binary search.

There is no need to keep track of already visited nodes because the potential successor (ans) is updated only when moving left, ensuring that we always have the closest higher value to p.val.

Additionally, no extra data structures are required, and the solution makes in-place updates without modifying the tree, hence the space complexity is O(1).

The algorithm terminates when we can no longer traverse the tree (when root is None), which means we can return the ans value as the in-order successor. If no such successor exists (i.e., p is the maximum value in the BST), the ans remains None, which the function returns as specified.

Here's a closer look at the code snippet which encapsulates the algorithm:

1class Solution:
2    def inorderSuccessor(self, root: TreeNode, p: TreeNode) -> Optional[TreeNode]:
3        ans = None
4        while root:
5            if root.val > p.val:
6                ans = root
7                root = root.left
8            else:
9                root = root.right
10        return ans

The single pass through the tree and constant time operations on each node's value guarantee the solution is time-efficient, running in O(h) time where h is the height of the tree. This effectively means that in the worst case scenario (a skewed tree), where the tree shape resembles a linked list, the algorithm could take O(n) time where n is the number of nodes, since the tree's height would be equivalent to the number of nodes.

Example Walkthrough

Let's illustrate the solution approach using a simple binary search tree and following the steps to find the in-order successor of a given node p. Consider the following BST:

1      4
2     / \
3    2   6
4   / \ / \
5  1  3 5  7

Let's find the in-order successor of the node p with a value of 3.

1. We start at the root of the tree, which is the node with the value 4.
2. We compare p.val (which is 3) with root.val (which is 4).
   • Since 4 is greater than 3, the node with 4 could be the in-order successor. We save this node and move to the left to look for an even closer value greater than 3.
3. Now, root is at the node with the value 2.
4. We compare p.val with the new root.val (2).
   • Since 2 is less than 3, we discard the left subtree including the current node and move right to find a larger value.
5. However, the right child of 2 is the node p itself. So, we move to the right subtree of p.
6. Because p doesn't have a right subtree, our loop terminates, and we return the stored ans, which is 4.

In this example, the in-order successor of node p with value 3 is the node with value 4.

Here's a breakdown of how the code snippet implements this logic:

1class Solution:
2    def inorderSuccessor(self, root: TreeNode, p: TreeNode) -> Optional[TreeNode]:
3        ans = None
4        while root:
5            if root.val > p.val:
6                ans = root  # Potentially a successor, so we update `ans`.
7                root = root.left  # Search for an even closer value on the left.
8            else:
9                root = root.right  # Current or left values are not greater, we go right.
10        return ans

This walk-through demonstrates the algorithm's ability to leverage the BST properties to efficiently find the in-order successor with minimal time complexity.

Solution Implementation

Time and Space Complexity

The time complexity of the given code is O(h) where h is the height of the binary search tree. This is because in the worst case, the while loop will traverse from root to the leaf, following one branch and visiting each level of the tree once.

The space complexity of the given code is O(1) because it does not use any additional space that is dependent on the size of the input tree. It only uses a fixed number of pointers regardless of the number of nodes in the tree.

Learn more about how to find time and space complexity quickly using problem constraints.