700614. Predecessor and Successor
Medium
Predecessor and Successor
Slug: predecessor-and-successor
Difficulty: Medium
Id: 700614
Topic Tags: Binary Search Tree, Tree, Data Structures
Company Tags: Ola Cabs
Summary
The problem is about finding the predecessor and successor of a given node in a Binary Search Tree (BST). The predecessor is the node with the highest value that is less than the given node, while the successor is the node with the lowest value that is greater than the given node. This problem involves traversing the BST to find these nodes.
Detailed Explanation
To solve this problem, we can use a recursive approach to traverse the BST and find the predecessor and successor of a given node.
Here's a step-by-step breakdown of the solution:
- Start at the root of the BST.
- If the given node is less than the root, it means the predecessor must be in the left subtree. Recursively call the function on the left child until we find a node that is greater than or equal to the given node. This node will be the predecessor.
- If the given node is greater than the root, it means the successor must be in the right subtree. Recursively call the function on the right child until we find a node that is less than or equal to the given node. This node will be the successor.
- If the given node is equal to the root, there are no predecessor and successor nodes.
Here's an ASCII art diagram of the BST:
8
/ \
3 10
/ \ / \
1 6 9 14
Time complexity: O(h), where h is the height of the BST. Space complexity: O(1), as we only use a constant amount of space to store variables.
Optimized Solutions
Java
public class Node {
int data;
Node left, right;
public Node(int item) {
data = item;
left = right = null;
}
}
public class PredecessorSuccessor {
static Node predecessor(Node root, int key) {
if (root == null) return null;
while (root.data > key && root.left != null) {
root = root.left;
}
return root;
}
static Node successor(Node root, int key) {
if (root == null) return null;
while (root.data < key && root.right != null) {
root = root.right;
}
return root;
}
}