Inorder predecessor and successor for a given key in BST

Introduction:

Binary Search Trees (BSTs) are powerful data structures used extensively in computer science for efficient searching, insertion, and deletion operations. One common task when working with BSTs is finding the inorder predecessor and successor for a given key.

Understanding Binary Search Trees (BSTs):

Before diving into inorder predecessors and successors, let's briefly review what a BST is. A binary search tree is a binary tree where each node has at most two children, commonly referred to as the left child and the right child. The key property of a BST is that for any node, all nodes in its left subtree have keys less than its own key, and all nodes in its right subtree have keys greater than its own key. This property makes searching, insertion, and deletion operations efficient, typically with a time complexity of O(log n) for balanced trees.

Inorder Traversal:

Inorder traversal is a method of visiting all nodes of a binary tree in ascending order of their keys. In a BST, inorder traversal naturally gives us the elements in sorted order. The order of traversal is: left child, root, right child.

Inorder Predecessor:

The inorder predecessor of a node in a BST is the node with the largest key that is smaller than the key of the given node. In other words, it is the rightmost node in the left subtree of the given node, or the maximum element in the left subtree.

Inorder Successor:

Similarly, the inorder successor of a node in a BST is the node with the smallest key that is larger than the key of the given node. It is the leftmost node in the right subtree of the given node, or the minimum element in the right subtree.

Illustration:

We want to find the inorder predecessor and successor of the node with key 11.

• Start from the root (20).
• Traverse left, as 11 is less than 20.
• Move to 9. Still, 11 is greater than 9, so move right.
• Arrive at 12. Since 11 is less than 12, move left.
• Reach 11. Now, the predecessor is 9, and the successor is 12.

Finding Inorder Predecessor and Successor:

To find the inorder predecessor and successor for a given key in a BST, we can perform a modified search operation.

• Search for the Given Key: We start by searching for the given key in the BST. If the key is found, then its inorder predecessor and successor can be determined based on the tree's structure.
• If the Key Has a Left Subtree: If the node corresponding to the given key has a left subtree, then the maximum element in this subtree will be the inorder predecessor.
• If the Key Has a Right Subtree: If the node corresponding to the given key has a right subtree, then the minimum element in this subtree will be the inorder successor.
• Handling Cases Where Node Has No Left or Right Subtree: If the node corresponding to the given key has no left subtree or no right subtree, we need to traverse up the tree until we find a node whose left child is the ancestor of the given node. This node will be the inorder predecessor. Similarly, if we need to find the successor, we traverse up the tree until we find a node whose right child is the ancestor of the given node. This node will be the inorder successor.

Implementation:

Explanation:

• The program defines a structure TreeNode to represent a node in a binary tree. Each node has an integer value (val) and pointers to its left and right child nodes.
• The Solution class contains a method findPredecessorSuccessor responsible for finding the predecessor and successor of a given key in a BST.
• The findPredecessorSuccessor method takes the root of the BST, references to pred and succ (which will be updated to point to the predecessor and successor respectively), and the key whose predecessor and successor are to be found.
• The method traverses the BST recursively. If the root is null, the function returns.
• If the root's value matches the key, it sets the predecessor to the maximum value in the left subtree and the successor to the minimum value in the right subtree.
• If the key is smaller than the current root's value, it explores the left subtree. Otherwise, it explores the right subtree.
• In the main function, a sample BST is created. Then, the findPredecessorSuccessor method is called to find the predecessor and successor of a given key (40 in this case).

Program Output:

Complexity Analysis:

The time complexity of finding the inorder predecessor and successor in a BST is O(h), where h is the height of the tree. In the worst-case scenario, when the tree is skewed, the height of the tree becomes equal to the number of nodes, resulting in O(n) time complexity. However, in well-balanced BSTs, the height is O(log n), leading to efficient operations.

Conclusion:

In conclusion, the algorithm efficiently finds the inorder predecessor and successor for a given key in a Binary Search Tree (BST) through recursive traversal. Leveraging the BST's structure, it determines the predecessor as the maximum value in the left subtree and the successor as the minimum value in the right subtree. With a time complexity of O(h), where h is the tree's height, it demonstrates optimal performance, especially in balanced trees, making it a reliable solution for various BST applications.