Find inorder predecessor for the given key in a BST
Given a BST, find the inorder predecessor of a given key in it. If the key does not lie in the BST, return the previous greater node (if any) present in the BST.
An inorder predecessor of a node in the BST is the previous node in the inorder traversal of it. For example, consider the following tree:
The inorder predecessor of 8 does not exist.
The inorder predecessor of 10 is 8
The inorder predecessor of 12 is 10
The inorder predecessor of 20 is 16
A node’s inorder predecessor is a node with maximum value in its left subtree, i.e., its left subtree’s right-most child. If the left subtree of the node doesn’t exist, then the inorder predecessor is one of its ancestors. To find which ancestors are the predecessor, move up the tree towards the root until we encounter a node that is the right child of its parent. If any such node is found, then the inorder predecessor is its parent; otherwise, the inorder predecessor does not exist for the node.
Recursive Version
We can recursively check the above conditions. The idea is to search for the given node in the tree and update the predecessor to the current node before visiting its right subtree. If the node is found in the BST, return the maximum value node in its left subtree. If the left subtree of the node doesn’t exist, then the inorder predecessor is one of its ancestors, which is already being updated while searching for the given key.
Following is the C++, Java, and Python implementation of the idea:
C++
|
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 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 101 102 103 104 105 106 107 108 109 |
#include <iostream> using namespace std; // Data structure to store a BST node struct Node { int data; Node* left = nullptr, *right = nullptr; Node() {} Node(int data): data(data) {} }; // Recursive function to insert a key into a BST Node* insert(Node* root, int key) { // if the root is null, create a new node and return it if (root == nullptr) { return new Node(key); } // if the given key is less than the root node, recur for the left subtree if (key < root->data) { root->left = insert(root->left, key); } // if the given key is more than the root node, recur for the right subtree else { root->right = insert(root->right, key); } return root; } // Helper function to find the maximum value node in a given BST Node* findMaximum(Node* root) { while (root->right) { root = root->right; } return root; } // Recursive function to find inorder predecessor for a given key in the BST Node* findPredecessor(Node* root, Node* prec, int key) { // base case if (root == nullptr) { return prec; } // if a node with the desired value is found, the predecessor is the maximum // value node in its left subtree (if any) if (root->data == key) { if (root->left != nullptr) { return findMaximum(root->left); } } // if the given key is less than the root node, recur for the left subtree else if (key < root->data) { return findPredecessor(root->left, prec, key); } // if the given key is more than the root node, recur for the right subtree else { // update predecessor to the current node before recursing // in the right subtree prec = root; return findPredecessor(root->right, prec, key); } return prec; } int main() { int keys[] = { 15, 10, 20, 8, 12, 16, 25 }; /* Construct the following tree 15 / \ / \ 10 20 / \ / \ / \ / \ 8 12 16 25 */ Node* root = nullptr; for (int key: keys) { root = insert(root, key); } // find inorder predecessor for each key for (int key: keys) { Node* prec = findPredecessor(root, nullptr, key); if (prec != nullptr) { cout << "The predecessor of node " << key << " is " << prec->data << endl; } else { cout << "The predecessor doesn't exist for " << key << endl; } } return 0; } |
Java
|
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 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 101 102 103 104 105 106 107 108 109 110 111 112 |
// A class to store a BST node class Node { int data; Node left = null, right = null; Node(int data) { this.data = data; } } class Main { // Recursive function to insert a key into a BST public static Node insert(Node root, int key) { // if the root is null, create a new node and return it if (root == null) { return new Node(key); } // if the given key is less than the root node, recur for the left subtree if (key < root.data) { root.left = insert(root.left, key); } // if the given key is more than the root node, recur for the right subtree else { root.right = insert(root.right, key); } return root; } // Helper function to find the maximum value node in a given BST public static Node findMaximum(Node root) { while (root.right != null) { root = root.right; } return root; } // Recursive function to find inorder predecessor for a given key in the BST public static Node findPredecessor(Node root, Node prec, int key) { // base case if (root == null) { return prec; } // if a node with the desired value is found, the predecessor is the maximum // value node in its left subtree (if any) if (root.data == key) { if (root.left != null) { return findMaximum(root.left); } } // if the given key is less than the root node, recur for the left subtree else if (key < root.data) { return findPredecessor(root.left, prec, key); } // if the given key is more than the root node, recur for the right subtree else { // update predecessor to the current node before recursing // in the right subtree prec = root; return findPredecessor(root.right, prec, key); } return prec; } public static void main(String[] args) { int[] keys = { 15, 10, 20, 8, 12, 16, 25 }; /* Construct the following tree 15 / \ / \ 10 20 / \ / \ / \ / \ 8 12 16 25 */ Node root = null; for (int key: keys) { root = insert(root, key); } // find inorder predecessor for each key for (int key: keys) { Node prec = findPredecessor(root, null, key); if (prec != null) { System.out.println("The predecessor of node " + key + " is " + prec.data); } else { System.out.println("The predecessor doesn't exist for node " + key); } } } } |
Python
|
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 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 |
# A class to store a BST node class Node: def __init__(self, data, left=None, right=None): self.data = data self.left = left self.right = right # Recursive function to insert a key into a BST def insert(root, key): # if the root is None, create a new node and return it if root is None: return Node(key) # if the given key is less than the root node, recur for the left subtree if key < root.data: root.left = insert(root.left, key) # if the given key is more than the root node, recur for the right subtree else: root.right = insert(root.right, key) return root # Helper function to find the maximum value node in a given BST def findMaximum(root): while root.right: root = root.right return root # Recursive function to find inorder predecessor for a given key in a BST def findPredecessor(root, prec, key): # base case if root is None: return prec # if a node with the desired value is found, the predecessor is the maximum value # node in its left subtree (if any) if root.data == key: if root.left: return findMaximum(root.left) # if the given key is less than the root node, recur for the left subtree elif key < root.data: return findPredecessor(root.left, prec, key) # if the given key is more than the root node, recur for the right subtree else: # update predecessor to the current node before recursing # in the right subtree prec = root return findPredecessor(root.right, prec, key) return prec if __name__ == '__main__': keys = [15, 10, 20, 8, 12, 16, 25] ''' Construct the following tree 15 / \ / \ 10 20 / \ / \ / \ / \ 8 12 16 25 ''' root = None for key in keys: root = insert(root, key) # find inorder predecessor for each key for key in keys: prec = findPredecessor(root, None, key) if prec: print(f'Predecessor of node {key} is {prec.data}') else: print('The predecessor doesn\'t exist for node', key) |
Output:
The predecessor of node 15 is 12
The predecessor of node 10 is 8
The predecessor of node 20 is 16
The predecessor doesn’t exist for node 8
The predecessor of node 12 is 10
The predecessor of node 16 is 15
The predecessor of node 25 is 20
The predecessor of node 15 is 12
The predecessor of node 10 is 8
The predecessor of node 20 is 16
The predecessor doesn’t exist for node 8
The predecessor of node 12 is 10
The predecessor of node 16 is 15
The predecessor of node 25 is 20
The time complexity of the above solution is O(n), where n is the size of the BST, and requires space proportional to the tree’s height for the call stack.
Iterative Version
The same algorithm can be easily implemented iteratively as follows in C++, Java, and Python:
C++
|
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 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 101 102 103 104 105 106 107 108 109 110 111 112 113 114 115 116 117 118 119 120 121 122 |
#include <iostream> using namespace std; // Data structure to store a BST node struct Node { int data; Node* left = nullptr, *right = nullptr; Node() {} Node(int data): data(data) {} }; // Recursive function to insert a key into a BST Node* insert(Node* root, int key) { // if the root is null, create a new node and return it if (root == nullptr) { return new Node(key); } // if the given key is less than the root node, recur for the left subtree if (key < root->data) { root->left = insert(root->left, key); } // if the given key is more than the root node, recur for the right subtree else { root->right = insert(root->right, key); } return root; } // Helper function to find the maximum value node in a given BST Node* findMaximum(Node* root) { while (root->right) { root = root->right; } return root; } // Iterative function to find inorder predecessor for a given key in a BST Node* findPredecessor(Node* root, int key) { // base case if (root == nullptr) { return nullptr; } Node* prec = nullptr; while (1) { // if the given key is less than the root node, visit the left subtree if (key < root->data) { root = root->left; } // if the given key is more than the root node, visit the right subtree else if (key > root->data) { // update predecessor to the current node before visiting // right subtree prec = root; root = root->right; } // if a node with the desired value is found, the predecessor is the maximum // value node in its left subtree (if any) else { if (root->left) { prec = findMaximum(root->left); } break; } // if the key doesn't exist in the binary tree, return previous greater node if (!root) { return prec; } } // return predecessor, if any return prec; } int main() { int keys[] = { 15, 10, 20, 8, 12, 16, 25 }; /* Construct the following tree 15 / \ / \ 10 20 / \ / \ / \ / \ 8 12 16 25 */ Node* root = nullptr; for (int key: keys) { root = insert(root, key); } // find inorder predecessor for each key for (int key: keys) { Node* prec = findPredecessor(root, key); if (prec != nullptr) { cout << "The predecessor of node " << key << " is " << prec->data << endl; } else { cout << "The predecessor doesn't exist for " << key << endl; } } return 0; } |
Java
|
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 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 101 102 103 104 105 106 107 108 109 110 111 112 113 114 115 116 117 118 119 120 121 122 123 124 125 |
// A class to store a BST node class Node { int data; Node left = null, right = null; Node(int data) { this.data = data; } } class Main { // Recursive function to insert a key into a BST public static Node insert(Node root, int key) { // if the root is null, create a new node and return it if (root == null) { return new Node(key); } // if the given key is less than the root node, recur for the left subtree if (key < root.data) { root.left = insert(root.left, key); } // if the given key is more than the root node, recur for the right subtree else { root.right = insert(root.right, key); } return root; } // Helper function to find the maximum value node in a given BST public static Node findMaximum(Node root) { while (root.right != null) { root = root.right; } return root; } // Iterative function to find inorder predecessor for a given key in the BST public static Node findPredecessor(Node root, int key) { // base case if (root == null) { return null; } Node prec = null; while (true) { // if the given key is less than the root node, visit the left subtree if (key < root.data) { root = root.left; } // if the given key is more than the root node, visit the right subtree else if (key > root.data) { // update predecessor to the current node before visiting // right subtree prec = root; root = root.right; } // if a node with the desired value is found, the predecessor is the // maximum value node in its left subtree (if any) else { if (root.left!= null) { prec = findMaximum(root.left); } break; } // if the key doesn't exist in the binary tree, // return previous greater node if (root == null) { return prec; } } // return predecessor, if any return prec; } public static void main(String[] args) { int[] keys = { 15, 10, 20, 8, 12, 16, 25 }; /* Construct the following tree 15 / \ / \ 10 20 / \ / \ / \ / \ 8 12 16 25 */ Node root = null; for (int key: keys) { root = insert(root, key); } // find inorder predecessor for each key for (int key: keys) { Node prec = findPredecessor(root, key); if (prec != null) { System.out.println("The predecessor of node " + key + " is " + prec.data); } else { System.out.println("The predecessor doesn't exist for node " + key); } } } } |
Python
|
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 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 |
# A class to store a BST node class Node: def __init__(self, data, left=None, right=None): self.data = data self.left = left self.right = right # Recursive function to insert a key into a BST def insert(root, key): # if the root is None, create a new node and return it if root is None: return Node(key) # if the given key is less than the root node, recur for the left subtree if key < root.data: root.left = insert(root.left, key) # if the given key is more than the root node, recur for the right subtree else: root.right = insert(root.right, key) return root # Function to find the maximum value node in a given BST def findMaximum(root): while root.right: root = root.right return root # Iterative function to find inorder predecessor for a given key in a BST def findPredecessor(root, key): # base case if not root: return None prec = None while True: # if the given key is less than the root node, visit the left subtree if key < root.data: root = root.left # if the given key is more than the root node, visit the right subtree elif key > root.data: # update predecessor to the current node before visiting # right subtree prec = root root = root.right # if a node with the desired value is found, the predecessor is the maximum # value node in its left subtree (if any) else: if root.left: prec = findMaximum(root.left) break # if the key doesn't exist in the binary tree, return previous greater node if root is None: return prec # return predecessor, if any return prec if __name__ == '__main__': keys = [15, 10, 20, 8, 12, 16, 25] ''' Construct the following tree 15 / \ / \ 10 20 / \ / \ / \ / \ 8 12 16 25 ''' root = None for key in keys: root = insert(root, key) # find inorder predecessor for each key for key in keys: prec = findPredecessor(root, key) if prec: print(f'Predecessor of node {key} is {prec.data}') else: print('The predecessor doesn\'t exist for node', key) |
Output:
The predecessor of node 15 is 12
The predecessor of node 10 is 8
The predecessor of node 20 is 16
The predecessor doesn’t exist for node 8
The predecessor of node 12 is 10
The predecessor of node 16 is 15
The predecessor of node 25 is 20
The predecessor of node 15 is 12
The predecessor of node 10 is 8
The predecessor of node 20 is 16
The predecessor doesn’t exist for node 8
The predecessor of node 12 is 10
The predecessor of node 16 is 15
The predecessor of node 25 is 20
The time complexity of the above solution is O(n), where n is the size of the BST. The auxiliary space required by the program is O(1).
Also See:
Update every key in a BST to contain the sum of all greater keys
Remove nodes from a BST that have keys outside a valid range
Thanks for reading.
To share your code in the comments, please use our online compiler that supports C, C++, Java, Python, JavaScript, C#, PHP, and many more popular programming languages.
Like us? Refer us to your friends and support our growth. Happy coding :)