Inorder Successor of a node in Binary Tree

Hello Everyone,

Given a binary tree and a node, we need to write a program to find inorder successor of this node.

Inorder Successor of a node in binary tree is the next node in Inorder traversal of the Binary Tree. Inorder Successor is NULL for the last node in Inoorder traversal.

We need to take care of 3 cases for any node to find its inorder successor as described below:

  1. Right child of node is not NULL. If the right child of the node is not NULL then the inorder successor of this node will be the leftmost node in it’s right subtree.
  2. Right Child of the node is NULL. If the right child of node is NULL. Then we keep finding the parent of the given node x, say p such that p->left = x. For example in the above given tree, inorder successor of node 5 will be 1 . First parent of 5 is 2 but 2->left != 5. So next parent of 2 is 1, now 1->left = 2. Therefore, inorder successor of 5 is 1.
    Below is the algorithm for this case:
  • Suppose the given node is x . Start traversing the tree from root node to find x recursively.
  • If root == x , stop recursion otherwise find x recursively for left and right subtrees.
  • Now after finding the node x , recur­sion will back­track to the root . Every recursive call will return the node itself to the calling function, we will store this in a temporary node say temp .Now, when it back­tracked to its par­ent which will be root now, check whether root.left = temp, if not , keep going up.
  1. If node is the rightmost node. If the node is the rightmost node in the given tree. For example, in the above tree node 6 is the right most node. In this case, there will be no inorder successor of this node. i.e. Inorder Successor of the rightmost node in a tree is NULL.

Below is the implementation of above approach:

// CPP program to find inorder successor of a node

#include<bits/stdc++.h>

using namespace std;

// A Binary Tree Node

struct Node

{

int data;

struct Node *left, *right;

};

// Temporary node for case 2

Node* temp = new Node;

// Utility function to create a new tree node

Node* newNode( int data)

{

Node *temp = new Node;

temp->data = data;

temp->left = temp->right = NULL;

return temp;

}

// function to find left most node in a tree

Node* leftMostNode(Node* node)

{

while (node != NULL && node->left != NULL)

node = node->left;

return node;

}

// function to find right most node in a tree

Node* rightMostNode(Node* node)

{

while (node != NULL && node->right != NULL)

node = node->right;

return node;

}

// recursive function to find the Inorder Scuccessor

// when the right child of node x is NULL

Node* findInorderRecursive(Node* root, Node* x )

{

if (!root)

return NULL;

if (root==x || (temp = findInorderRecursive(root->left,x)) ||

(temp = findInorderRecursive(root->right,x)))

{

if (temp)

{

if (root->left == temp)

{

cout << "Inorder Successor of " << x->data;

cout << " is " << root->data << "\n" ;

return NULL;

}

}

return root;

}

return NULL;

}

// function to find inorder successor of

// a node

void inorderSuccesor(Node* root, Node* x)

{

// Case1: If right child is not NULL

if (x->right != NULL)

{

Node* inorderSucc = leftMostNode(x->right);

cout<< "Inorder Successor of " <<x->data<< " is " ;

cout<<inorderSucc->data<< "\n" ;

}

// Case2: If right child is NULL

if (x->right == NULL)

{

int f = 0;

Node* rightMost = rightMostNode(root);

// case3: If x is the right most node

if (rightMost == x)

cout << "No inorder successor! Right most node.\n" ;

else

findInorderRecursive(root, x);

}

}

// Driver program to test above functions

int main()

{

// Let's construct the binary tree

// as shown in above diagram

Node* root = newNode(1);

root->left = newNode(2);

root->right = newNode(3);

root->left->left = newNode(4);

root->left->right = newNode(5);

root->right->right = newNode(6);

// Case 1

inorderSuccesor(root, root->right);

// case 2

inorderSuccesor(root, root->left->left);

// case 3

inorderSuccesor(root, root->right->right);

return 0;

}

Output:

Inorder Successor of 3 is 6 Inorder Successor of 4 is 2 No inorder successor! Right most node.

Thankyou.