There is BST given with root node with key part as integer only. The structure of each node is as follows:
C++
struct Node
{
int key;
struct Node *left, *right ;
};
Java
static class Node
{
int key;
Node left, right ;
};
Python3
class Node:
def __init__(self, key):
self.key = key
self.left = None
self.right = None
C#
public class Node
{
public int key;
public Node left, right ;
};
Javascript
<script>
class Node {
constructor() {
this.key = 0;
this.left = null;
this.right = null;
}
}
</script>
You need to find the inorder successor and predecessor of a given key. In case the given key is not found in BST, then return the two values within which this key will lie.
Following is the algorithm to reach the desired result. It is a recursive method:
Input: root node, key output: predecessor node, successor node 1. If root is NULL then return 2. if key is found then a. If its left subtree is not null Then predecessor will be the right most child of left subtree or left child itself. b. If its right subtree is not null The successor will be the left most child of right subtree or right child itself. return 3. If key is smaller than root node set the successor as root search recursively into left subtree else set the predecessor as root search recursively into right subtreeFollowing is the implementation of the above algorithm:
C++
#include <iostream>
using namespace std;
struct Node
{
int key;
struct Node *left, *right;
};
void findPreSuc(Node* root, Node*& pre, Node*& suc, int key)
{
if (root == NULL) return ;
if (root->key == key)
{
if (root->left != NULL)
{
Node* tmp = root->left;
while (tmp->right)
tmp = tmp->right;
pre = tmp ;
}
if (root->right != NULL)
{
Node* tmp = root->right ;
while (tmp->left)
tmp = tmp->left ;
suc = tmp ;
}
return ;
}
if (root->key > key)
{
suc = root ;
findPreSuc(root->left, pre, suc, key) ;
}
else
{
pre = root ;
findPreSuc(root->right, pre, suc, key) ;
}
}
Node *newNode(int item)
{
Node *temp = new Node;
temp->key = item;
temp->left = temp->right = NULL;
return temp;
}
Node* insert(Node* node, int key)
{
if (node == NULL) return newNode(key);
if (key < node->key)
node->left = insert(node->left, key);
else
node->right = insert(node->right, key);
return node;
}
int main()
{
int key = 65;
Node *root = NULL;
root = insert(root, 50);
insert(root, 30);
insert(root, 20);
insert(root, 40);
insert(root, 70);
insert(root, 60);
insert(root, 80);
Node* pre = NULL, *suc = NULL;
findPreSuc(root, pre, suc, key);
if (pre != NULL)
cout << "Predecessor is " << pre->key << endl;
else
cout << "No Predecessor";
if (suc != NULL)
cout << "Successor is " << suc->key;
else
cout << "No Successor";
return 0;
}
Java
class GFG{
static class Node
{
int key;
Node left, right;
public Node()
{}
public Node(int key)
{
this.key = key;
this.left = this.right = null;
}
};
static Node pre = new Node(), suc = new Node();
static void findPreSuc(Node root, int key)
{
if (root == null)
return;
if (root.key == key)
{
if (root.left != null)
{
Node tmp = root.left;
while (tmp.right != null)
tmp = tmp.right;
pre = tmp;
}
if (root.right != null)
{
Node tmp = root.right;
while (tmp.left != null)
tmp = tmp.left;
suc = tmp;
}
return;
}
if (root.key > key)
{
suc = root;
findPreSuc(root.left, key);
}
else
{
pre = root;
findPreSuc(root.right, key);
}
}
static Node insert(Node node, int key)
{
if (node == null)
return new Node(key);
if (key < node.key)
node.left = insert(node.left, key);
else
node.right = insert(node.right, key);
return node;
}
public static void main(String[] args)
{
int key = 65;
Node root = new Node();
root = insert(root, 50);
insert(root, 30);
insert(root, 20);
insert(root, 40);
insert(root, 70);
insert(root, 60);
insert(root, 80);
findPreSuc(root, key);
if (pre != null)
System.out.println("Predecessor is " + pre.key);
else
System.out.println("No Predecessor");
if (suc != null)
System.out.println("Successor is " + suc.key);
else
System.out.println("No Successor");
}
}
Python
class Node:
def __init__(self, key):
self.key = key
self.left = None
self.right = None
def findPreSuc(root, key):
if root is None:
return
if root.key == key:
if root.left is not None:
tmp = root.left
while(tmp.right):
tmp = tmp.right
findPreSuc.pre = tmp
if root.right is not None:
tmp = root.right
while(temp.left):
tmp = tmp.left
findPreSuc.suc = tmp
return
if root.key > key :
findPreSuc.suc = root
findPreSuc(root.left, key)
else:
findPreSuc.pre = root
findPreSuc(root.right, key)
def insert(node , key):
if node is None:
return Node(key)
if key < node.key:
node.left = insert(node.left, key)
else:
node.right = insert(node.right, key)
return node
key = 65
root = None
root = insert(root, 50)
insert(root, 30);
insert(root, 20);
insert(root, 40);
insert(root, 70);
insert(root, 60);
insert(root, 80);
findPreSuc.pre = None
findPreSuc.suc = None
findPreSuc(root, key)
if findPreSuc.pre is not None:
print "Predecessor is", findPreSuc.pre.key
else:
print "No Predecessor"
if findPreSuc.suc is not None:
print "Successor is", findPreSuc.suc.key
else:
print "No Successor"
C#
using System;
public class GFG
{
public
class Node
{
public
int key;
public
Node left, right;
public Node()
{}
public Node(int key)
{
this.key = key;
this.left = this.right = null;
}
};
static Node pre = new Node(), suc = new Node();
static void findPreSuc(Node root, int key)
{
if (root == null)
return;
if (root.key == key)
{
if (root.left != null)
{
Node tmp = root.left;
while (tmp.right != null)
tmp = tmp.right;
pre = tmp;
}
if (root.right != null)
{
Node tmp = root.right;
while (tmp.left != null)
tmp = tmp.left;
suc = tmp;
}
return;
}
if (root.key > key)
{
suc = root;
findPreSuc(root.left, key);
}
else
{
pre = root;
findPreSuc(root.right, key);
}
}
static Node insert(Node node, int key)
{
if (node == null)
return new Node(key);
if (key < node.key)
node.left = insert(node.left, key);
else
node.right = insert(node.right, key);
return node;
}
public static void Main(String[] args)
{
int key = 65;
Node root = new Node();
root = insert(root, 50);
insert(root, 30);
insert(root, 20);
insert(root, 40);
insert(root, 70);
insert(root, 60);
insert(root, 80);
findPreSuc(root, key);
if (pre != null)
Console.WriteLine("Predecessor is " + pre.key);
else
Console.WriteLine("No Predecessor");
if (suc != null)
Console.WriteLine("Successor is " + suc.key);
else
Console.WriteLine("No Successor");
}
}
Javascript
<script>
class Node
{
constructor(key)
{
this.key = key;
this.left = this.right = null;
}
}
var pre = new Node(), suc = new Node();
function findPreSuc(root , key)
{
if (root == null)
return;
if (root.key == key)
{
if (root.left != null)
{
var tmp = root.left;
while (tmp.right != null)
tmp = tmp.right;
pre = tmp;
}
if (root.right != null)
{
var tmp = root.right;
while (tmp.left != null)
tmp = tmp.left;
suc = tmp;
}
return;
}
if (root.key > key)
{
suc = root;
findPreSuc(root.left, key);
}
else
{
pre = root;
findPreSuc(root.right, key);
}
}
function insert(node , key)
{
if (node == null)
return new Node(key);
if (key < node.key)
node.left = insert(node.left, key);
else
node.right = insert(node.right, key);
return node;
}
var key = 65;
var root = new Node();
root = insert(root, 50);
insert(root, 30);
insert(root, 20);
insert(root, 40);
insert(root, 70);
insert(root, 60);
insert(root, 80);
findPreSuc(root, key);
if (pre != null)
document.write("Predecessor is " + pre.key);
else
document.write("No Predecessor");
if (suc != null)
document.write("<br/>Successor is " + suc.key);
else
document.write("<br/>No Successor");
</script>
Output:
Predecessor is 60 Successor is 70Complexity Analysis:
Time
Complexity: O(h), where h is the height of the tree. In the worst case as explained above we travel the whole height of the tree.
Auxiliary Space: O(1), since no extra space has been taken.
Another Approach:
We can also find the inorder successor and inorder predecessor using inorder traversal. Check if the current node is smaller than the given key for the predecessor and for a successor, check if it is greater than the given key. If it is greater than the given key then, check if it is smaller than the already stored value in the successor then, update it. At last, get the predecessor and successor stored in q(successor) and p(predecessor).
C++
#include<iostream>
#include<stdlib.h>
using namespace std;
struct Node
{
int data;
Node* left,*right;
};
Node* getnode(int info)
{
Node* p = (Node*)malloc(sizeof(Node));
p->data = info;
p->right = NULL;
p->left = NULL;
return p;
}
void find_p_s(Node* root,int a,
Node** p, Node** q)
{
if(!root)
return ;
find_p_s(root->left, a, p, q);
if(root&&root->data > a)
{
if((!*q) || (*q) && (*q)->data > root->data)
*q = root;
}
else if(root && root->data < a)
{
*p = root;
}
find_p_s(root->right, a, p, q);
}
int main()
{
Node* root1 = getnode(50);
root1->left = getnode(20);
root1->right = getnode(60);
root1->left->left = getnode(10);
root1->left->right = getnode(30);
root1->right->left = getnode(55);
root1->right->right = getnode(70);
Node* p = NULL, *q = NULL;
find_p_s(root1, 55, &p, &q);
if(p)
cout << p->data;
if(q)
cout << " " << q->data;
return 0;
}
Java
import java.util.*;
class GFG{
static class Node
{
int data;
Node left,right;
};
static Node getnode(int info)
{
Node p = new Node();
p.data = info;
p.right = null;
p.left = null;
return p;
}
static Node p,q;
static void find_p_s(Node root,int a)
{
if(root == null)
return ;
find_p_s(root.left, a);
if(root != null && root.data > a)
{
if((q == null) || (q != null) && q.data > root.data)
q = root;
}
else if(root != null && root.data < a)
{
p = root;
}
find_p_s(root.right, a);
}
public static void main(String[] args)
{
Node root1 = getnode(50);
root1.left = getnode(20);
root1.right = getnode(60);
root1.left.left = getnode(10);
root1.left.right = getnode(30);
root1.right.left = getnode(55);
root1.right.right = getnode(70);
p = null;
q = null;
find_p_s(root1, 55);
if(p != null)
System.out.print(p.data);
if(q != null)
System.out.print(" " + q.data);
}
}
Python3
class getnode:
def __init__(self, data):
self.data = data
self.left = None
self.right = None
def find_p_s(root, a, p, q):
if(not root):
return
find_p_s(root.left, a, p, q)
if(root and root.data > a):
if((not q[0]) or q[0] and
q[0].data > root.data):
q[0] = root
elif(root and root.data < a):
p[0]= root
find_p_s(root.right, a, p, q)
if __name__ == '__main__':
root1 = getnode(50)
root1.left = getnode(20)
root1.right = getnode(60)
root1.left.left = getnode(10)
root1.left.right = getnode(30)
root1.right.left = getnode(55)
root1.right.right = getnode(70)
p = [None]
q = [None]
find_p_s(root1, 55, p, q)
if(p[0]) :
print(p[0].data, end = "")
if(q[0]) :
print("", q[0].data)
C#
using System;
public class GFG {
public class Node {
public int data;
public Node left, right;
};
static Node getnode(int info) {
Node p = new Node();
p.data = info;
p.right = null;
p.left = null;
return p;
}
static Node p, q;
static void find_p_s(Node root, int a)
{
if (root == null)
return;
find_p_s(root.left, a);
if (root != null && root.data > a) {
if ((q == null) || (q != null) && q.data > root.data)
q = root;
}
else if (root != null && root.data < a) {
p = root;
}
find_p_s(root.right, a);
}
public static void Main(String[] args) {
Node root1 = getnode(50);
root1.left = getnode(20);
root1.right = getnode(60);
root1.left.left = getnode(10);
root1.left.right = getnode(30);
root1.right.left = getnode(55);
root1.right.right = getnode(70);
p = null;
q = null;
find_p_s(root1, 55);
if (p != null)
Console.Write(p.data);
if (q != null)
Console.Write(" " + q.data);
}
}
Javascript
<script>
class Node
{
constructor(data)
{
this.data = data;
this.left = this.right = null;
}
}
function find_p_s(root, a, p, q)
{
if(root == null)
return
find_p_s(root.left, a, p, q)
if(root && root.data > a)
{
if((q[0] == null) || q[0] != null && q[0].data > root.data)
q[0] = root
}
else if(root && root.data < a)
{ p[0] = root
}
find_p_s(root.right, a, p, q)
}
let root1 = new Node(50)
root1.left = new Node(20)
root1.right = new Node(60)
root1.left.left = new Node(10)
root1.left.right = new Node(30)
root1.right.left = new Node(55)
root1.right.right = new Node(70)
p = [null]
q = [null]
find_p_s(root1, 55, p, q)
if(p[0] != null)
document.write(p[0].data, end = " ")
if(q[0] != null)
document.write(" ", q[0].data)
</script>
Output :
50 60Complexity Analysis:
Time Complexity:
O(n), where n is the total number of nodes in the tree. In the worst case as explained above we travel the whole tree.
Auxiliary Space: O(n).
?list=PLqM7alHXFySHCXD7r1J0ky9Zg_GBB1dbk
This article is contributed by algoLover. Please write comments if you find anything incorrect, or you want to share more information about the topic discussed above.