Where is the inorder predecessor of a node A in a binary search tree?

There is BST given with root node with key part as integer only. The structure of each node is as follows:

Índice Show

Where is the inorder successor of a node A in a binary search tree?
Where is the predecessor in a binary search tree?
Where are inorder predecessor and inorder successor stored in a binary search tree?
What is inorder predecessor in binary tree?

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 subtree

Following 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 70

Complexity 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 60

Complexity 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.

Where is the inorder successor of a node A in a binary search tree?

In Binary Tree, Inorder successor of a node is the next node in Inorder traversal of the Binary Tree. Inorder Successor is NULL for the last node in Inorder traversal. In Binary Search Tree, Inorder Successor of an input node can also be defined as the node with the smallest key greater than the key of the input node.

Where is the predecessor in a binary search tree?

Where is the predecessor of a node in a tree, assuming all keys are distinct? If X has two children, its predecessor is the maximum value in its left subtree and its successor the minimum value in its right subtree. If it does not have a left child, a node's predecessor is its rst left ancestor.

Where are inorder predecessor and inorder successor stored in a binary search tree?

When you do the inorder traversal of a binary tree, the neighbors of given node are called Predecessor(the node lies behind of given node) and Successor (the node lies ahead of given node). Approach: Say you have to find the inorder predecessor and successor node 15. First compare the 15 with root (25 here).

What is inorder predecessor in binary tree?

The inorder predecessor of a node p is the node q that comes just before p in the binary tree's inorder traversal. Given the root node of a binary search tree and the node p , find the inorder predecessor of node p . If it does not exist, return null .