gptAI
Home

Inorder Successor In BST: LeetCode Guide & Solutions

9 min read 11-15- 2024
Inorder Successor In BST: LeetCode Guide & Solutions

Table of Contents :

In a binary search tree (BST), each node has a maximum of two children: a left child and a right child. The left child contains values less than the parent node, while the right child contains values greater than the parent node. This structure allows for efficient searching, insertion, and deletion operations. One important concept within BSTs is the inorder successor.

What is Inorder Successor?

The inorder successor of a node in a binary search tree is the node that would appear immediately after it in an in-order traversal of the tree. To visualize this, an in-order traversal of a BST visits nodes in the following order: left subtree, then the current node, followed by the right subtree. This means that the inorder successor of a given node is:

  • The smallest node in the right subtree if it exists.
  • The lowest ancestor of the node whose left child is also an ancestor of the node.

Understanding the inorder successor is vital for various operations in a binary search tree, such as deletion and finding the next larger element.

Why Do We Need to Find the Inorder Successor?

Knowing how to find the inorder successor is useful in several scenarios:

  1. Deleting a Node: When deleting a node with two children, you need to find its inorder successor to replace it.
  2. Finding Next Greater Element: In problems requiring the next greater element than a specific value, the inorder successor plays a crucial role.

Finding Inorder Successor in a BST: Steps

Step 1: Check if Right Subtree Exists

If the node has a right child, the inorder successor is the minimum value node in the right subtree. The process to find it includes:

  • Move to the right child of the current node.
  • Continue moving to the left child until no more left children are found.

Step 2: No Right Subtree

If the node does not have a right child, the successor is one of the node's ancestors. The algorithm to find the inorder successor in this case involves:

  • Start from the root and traverse down the tree.
  • Keep track of the last node you encountered that is greater than the given node.
  • If you reach a node that is less than the given node, stop updating the successor.

Visual Example

Consider the following BST:

       20
      /  \
    10    30
   / \    / \
  5  15 25  35

If we want to find the inorder successor of the node with value 20:

  • Step 1: Move to the right child (30). It has no left child, thus the inorder successor of 20 is 30.

If we want to find the inorder successor of the node with value 10:

  • Step 1: Move to the right child (15). It has no left child, thus the inorder successor of 10 is 15.

If we want to find the inorder successor of the node with value 35:

  • Step 2: Since it has no right child, traverse to the root (20) to find the last node that is greater than 35, which is 20.

LeetCode Problem: Inorder Successor in BST

LeetCode offers a challenge related to finding the inorder successor in a BST. The problem statement typically looks like this:

Given a binary search tree and a node in it, find the in-order successor of that node in the BST.

The successor of a node is the node with the smallest key greater than the key of the given node.

Example Input and Output

  • Input: A BST and a node
  • Output: The inorder successor of the provided node

Constraints

  • The binary search tree is valid.
  • The node is guaranteed to be in the tree.

Sample Test Cases

Here’s a sample table for reference:

<table> <tr> <th>Input BST</th> <th>Node Value</th> <th>Inorder Successor</th> </tr> <tr> <td> <pre> 20 /
10 30 / \ /
5 15 25 35 </pre> </td> <td>15</td> <td>20</td> </tr> <tr> <td> <pre> 20 /
10 30 / \ /
5 15 25 35 </pre> </td> <td>30</td> <td>35</td> </tr> <tr> <td> <pre> 20 /
10 30 / \ /
5 15 25 35 </pre> </td> <td>35</td> <td>null</td> </tr> </table>

Solution Approach

To solve the problem on LeetCode, we can use either a recursive or an iterative approach. Below are the implementations for both methods.

Recursive Approach

class Solution:
    def inorderSuccessor(self, root: TreeNode, p: TreeNode) -> TreeNode:
        if not root:
            return None
            
        if p.val >= root.val:
            return self.inorderSuccessor(root.right, p)
        
        left = self.inorderSuccessor(root.left, p)
        return left if left else root

Iterative Approach

class Solution:
    def inorderSuccessor(self, root: TreeNode, p: TreeNode) -> TreeNode:
        successor = None
        
        while root:
            if p.val >= root.val:
                root = root.right
            else:
                successor = root
                root = root.left
        
        return successor

Key Points to Remember

  • If the node has a right child, the inorder successor is the minimum value node in that subtree.
  • If the node does not have a right child, traverse up the tree to find the last ancestor that is greater than the node.
  • The time complexity for both approaches is O(h), where h is the height of the tree.

Conclusion

Understanding the concept of the inorder successor in a binary search tree is essential for efficiently solving various problems related to BSTs, such as deletions and finding next larger elements. With this guide, you should be well-equipped to tackle any LeetCode problems related to finding the inorder successor. Utilizing the approaches mentioned, you can achieve an optimal solution while enhancing your skills in binary search trees and algorithms.

Incorporate these insights into your coding practice to further solidify your understanding of binary search trees and their operations. Happy coding! 🎉

Featured Posts