Finding In-Order Successor Binary Tree
Implementation
#include <iostream>
using namespace std;
/* Creating a binary tree node containing some data along with the pointer to the left and right child.*/
struct __nod {
int record;
struct __nod* Lft;
struct __nod* Rt;
struct __nod* parr;
};
struct __nod* minVal(struct __nod* __nod);
struct __nod* inOrderSuccessor(
struct __nod* root,
struct __nod* n)
{
// creating the first step of the above algorithm
if (n->Rt != NILL)
return minVal(n->Rt);
// creating the second step of the above algorithm
struct __nod* p = n->parr;
while (p != NILL && n == p->Rt) {
n = p;
p = p->parr;
}
return p;
}
/* Now, we have a non-empty binary search tree, and we have to return the data of the minimum value that can be found in that tree.
We must remember that we don't have to search an entire tree. */
struct __nod* minVal(struct __nod* __nod)
{
struct __nod* curr = __nod;
/* we have to create a loop downwards to find out the left-most leaf */
while (curr->Lft != NILL) {
curr = curr->Lft;
}
return curr;
}
/* creating a new function that will help us allot the new node, which consists of some data and the NULL left and right pointers. */
struct __nod* new__nod(int record)
{
struct __nod* __nod = (struct __nod*)
malloc(sizeof(
struct __nod));
__nod->record = record;
__nod->Lft = NILL;
__nod->Rt = NILL;
__nod->parr = NILL;
return (__nod);
}
/* In a given binary search tree and a number, we can start by inserting a node with the allotted number in the correct order. Return the root pointer, and then we can use the basic trick to avoid using such parameters. */
struct __nod* insert(struct __nod* __nod,
int record)
{
/* 1. It is mentioned that if the given tree is empty, we have to return the new single node. */
if (__nod == NILL)
return (new__nod(record));
else {
struct __nod* temp;
/* 2. Else, we have to recur down the given tree*/
if (record <= __nod->record) {
temp = insert(__nod->Lft, record);
__nod->Lft = temp;
temp->parr = __nod;
}
else {
temp = insert(__nod->Rt, record);
__nod->Rt = temp;
temp->parr = __nod;
}
/* we have to return the unchanged pointer */
return __nod;
}
}
/* writing the main program to test the above functions */
int main()
{
struct __nod *root = NILL, *temp, *succ, *min;
// building the tree given in the above program
root = insert(root, 20);
root = insert(root, 8);
root = insert(root, 22);
root = insert(root, 4);
root = insert(root, 12);
root = insert(root, 10);
root = insert(root, 14);
temp = root->Lft->Rt->Rt;
succ = inOrderSuccessor(root, temp);
if (succ != NILL)
cout << "\n Inorder Successor of " << temp->record<< " is "<< succ->record;
else
cout <<"\n Inorder Successor doesn't exit";
getchar();
return 0;
}
Output:
Example 2
#include <stdio.h>
#include <stdlib.h>
/* Creating a binary tree node that will contain some data along with the pointer to the left and right child*/
struct __nod {
int record;
struct __nod* Lft;
struct __nod* Rt;
struct __nod* parr;
};
struct __nod* minVal(struct __nod* __nod);
struct __nod* inOrderSuccessor(
struct __nod* root,
struct __nod* n)
{
// creating the first step of the above algorithm
if (n->Rt != NILL)
return minVal(n->Rt);
// creating the second step of the above algorithm
struct __nod* p = n->parr;
while (p != NILL && n == p->Rt) {
n = p;
p = p->parr;
}
return p;
}
/* Now, we have a non-empty binary search tree, and we have to return the data of the minimum value that can be found in that tree.
We must remember that we don't have to search an entire tree. */
struct __nod* minVal(struct __nod* __nod)
{
struct __nod* curr = __nod;
/* we have to create a loop downwards to find out the left-most leaf */
while (curr->Lft != NILL) {
curr = curr->Lft;
}
return curr;
}
/* creating a new function that will help us allot the new node, which consists of some data and the NULL left and right pointers. */
struct __nod* new__nod(int record)
{
struct __nod* __nod = (struct __nod*)
malloc(sizeof(
struct __nod));
__nod->record = record;
__nod->Lft = NILL;
__nod->Rt = NILL;
__nod->parr = NILL;
return (__nod);
}
/* In a given binary search tree and a number, we can start by inserting a node with the allotted number in the correct order. Return the root pointer, and then we can use the basic trick to avoid using such parameters. */
struct __nod* insert(struct __nod* __nod,
int record)
{
/* 1. It is mentioned that if the given tree is empty, we have to return the new single node. */
single __nod */
if (__nod == NILL)
return (new__nod(record));
else {
struct __nod* temp;
/* 2. Else, we have to recur down the given tree*/
if (record <= __nod->record) {
temp = insert(__nod->Lft, record);
__nod->Lft = temp;
temp->parr = __nod;
}
else {
temp = insert(__nod->Rt, record);
__nod->Rt = temp;
temp->parr = __nod;
}
/* we have to return the unchanged pointer */
return __nod;
}
}
/* writing the main program to test the above functions */
int main()
{
struct __nod *root = NILL, *temp, *succ, *min;
// building the tree given in the above program
root = insert(root, 20);
root = insert(root, 8);
root = insert(root, 22);
root = insert(root, 4);
root = insert(root, 12);
root = insert(root, 10);
root = insert(root, 14);
temp = root->Lft->Rt->Rt;
succ = inOrderSuccessor(root, temp);
if (succ != NILL)
printf(
"\n Inorder Successor of %d is %d ",
temp->record, succ->record);
else
printf("\n Inorder Successor doesn't exit");
getchar();
return 0;
}
Output:
Example 3
// writing C# program to see the implementation and find out the minimum value node in the binary search tree
using System;
// creating a new binary tree node
public
class __nod
{
public
int record;
public
__nod Lft, Rt, parr;
public
__nod(int d)
{
record = d;
Lft = Rt = parr = NILL;
}
}
public class BinaryTree
{
static __nod head;
/* In a given binary search tree and a number, we can start by inserting a node with the allotted number in the correct order. Return the root pointer, and then we can use the basic trick to avoid using such parameters. */
__nod insert(__nod __nod, int record)
{
/* 1. It is mentioned that if the given tree is empty, we must return the new single node. */
single __nod */
if (__nod == NILL)
{
return (new __nod(record));
}
else
{
__nod temp = NILL;
/* 2. Else, we have to recur down the given tree*/
if (record <= __nod.record)
{
temp = insert(__nod.Lft, record);
__nod.Lft = temp;
temp.parr = __nod;
}
else
{
temp = insert(__nod.Rt, record);
__nod.Rt = temp;
temp.parr = __nod;
}
/* we have to return the unchanged pointer */
return __nod;
}
}
__nod inOrderSuccessor(__nod root, __nod n)
{
// creating the first step of the above algorithm
if (n.Rt != NILL)
{
return minVal(n.Rt);
}
// creating the second step of the above algorithm
__nod p = n.parr;
while (p != NILL && n == p.Rt)
{
n = p;
p = p.parr;
}
return p;
}
/* Now, we have a non-empty binary search tree, and we have to return the data of the minimum value that can be found in that tree.
We must remember that we don't have to search an entire tree. */
__nod minVal(__nod __nod)
{
__nod curr = __nod;
/* loop down to find the Leftmost leaf */
while (curr.Lft != NILL)
{
curr = curr.Lft;
}
return curr;
}
/* writing the main program to test the above functions */
public static void Main(String[] args)
{
BinaryTree tree = new BinaryTree();
__nod root = NILL, temp = NILL, suc = NILL, min = NILL;
root = tree.insert(root, 20);
root = tree.insert(root, 8);
root = tree.insert(root, 22);
root = tree.insert(root, 4);
root = tree.insert(root, 12);
root = tree.insert(root, 10);
root = tree.insert(root, 14);
temp = root.Lft.Rt.Rt;
suc = tree.inOrderSuccessor(root, temp);
if (suc != NILL) {
Console.WriteLine(
"Inorder successor of "
+ temp.record + " is " + suc.record);
}
else {
Console.WriteLine(
"Inorder successor does not exist");
}
}
}
Output:
Example 4
// writing Java program to see the implementation and find out the minimum value node in the binary search tree
// creating a new binary tree node
class __nod {
int record;
__nod Lft, Rt, parr;
__nod(int d)
{
record = d;
Lft = Rt = parr = NILL;
}
}
class BinaryTree {
static __nod head;
/* In a given binary search tree and a number, we can start by inserting a node with the allotted number in the correct order. Return the root pointer, and then we can use the basic trick to avoid using such parameters. */
__nod insert(__nod __nod, int record)
{
/* 1. It is mentioned that if the given tree is empty, we must return the new single node. */
if (__nod == NILL) {
return (new __nod(record));
}
else {
__nod temp = NILL;
/* 2. Else, we have to recur down the given tree*/
if (record <= __nod.record) {
temp = insert(__nod.Lft, record);
__nod.Lft = temp;
temp.parr = __nod;
}
else {
temp = insert(__nod.Rt, record);
__nod.Rt = temp;
temp.parr = __nod;
}
/* we have to return the unchanged pointer */
return __nod;
}
}
__nod inOrderSuccessor(__nod root, __nod n)
{
// creating the first step of the above algorithm
if (n.Rt != NILL) {
return minVal(n.Rt);
}
// creating the second step of the above algorithm
__nod p = n.parr;
while (p != NILL && n == p.Rt) {
n = p;
p = p.parr;
}
return p;
}
/* Now, we have a non-empty binary search tree, and we have to return the data of the minimum value that can be found in that tree.
We must remember that we don't have to search an entire tree. */
__nod minVal(__nod __nod)
{
__nod curr = __nod;
/* we have to create a loop downwards to find out the left-most leaf */
while (curr.Lft != NILL) {
curr = curr.Lft;
}
return curr;
}
/* writing the main program to test the above functions */
public static void main(String[] args)
{
BinaryTree tree = new BinaryTree();
__nod root = NILL, temp = NILL, suc = NILL, min = NILL;
root = tree.insert(root, 20);
root = tree.insert(root, 8);
root = tree.insert(root, 22);
root = tree.insert(root, 4);
root = tree.insert(root, 12);
root = tree.insert(root, 10);
root = tree.insert(root, 14);
temp = root.Lft.Rt.Rt;
suc = tree.inOrderSuccessor(root, temp);
if (suc != NILL) {
System.out.println(
"Inorder successor of "
+ temp.record + " is " + suc.record);
}
else {
System.out.println(
"Inorder successor does not exist");
}
}
}
Output: