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.
In the above diagram, inorder successor of node 4 is 2 and node 5 is 1.
We have already discussed how to find the inorder successor of a node in Binary Search Tree. We can not use the same approach to find the inorder successor in general Binary trees.
We need to take care of 3 cases for any node to find its inorder successor as described below:
- 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.
- 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, recursion will backtrack 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 backtracked to its parent which will be root now, check whether root.left = temp, if not , keep going up
.
- 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:
C++
// 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 << "
" ; 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<< "
" ; } // 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.
" ; 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; } |
Java
// Java program to find inorder successor of a node class Solution { // A Binary Tree Node static class Node { int data; Node left, right; } // Temporary node for case 2 static Node temp = new Node(); // Utility function to create a new tree node static 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 static Node leftMostNode(Node node) { while (node != null && node.left != null ) node = node.left; return node; } // function to find right most node in a tree static 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 static Node findInorderRecursive(Node root, Node x ) { if (root== null ) return null ; if (root==x || (temp = findInorderRecursive(root.left,x))!= null || (temp = findInorderRecursive(root.right,x))!= null ) { if (temp!= null ) { if (root.left == temp) { System.out.print( "Inorder Successor of " +x.data); System.out.print( " is " + root.data + "
" ); return null ; } } return root; } return null ; } // function to find inorder successor of // a node static void inorderSuccesor(Node root, Node x) { // Case1: If right child is not null if (x.right != null ) { Node inorderSucc = leftMostNode(x.right); System.out.print( "Inorder Successor of " +x.data+ " is " ); System.out.print(inorderSucc.data+ "
" ); } // 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) System.out.print( "No inorder successor! Right most node.
" ); else findInorderRecursive(root, x); } } // Driver program to test above functions public static void main(String args[]) { // Let's con 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); } } //contributed by Arnab Kundu |
Python3
""" Python3 code for inorder succesor and predecessor of tree """ # A Binary Tree Node # Utility function to create a new tree node class newNode: # Constructor to create a new node def __init__( self , data): self .data = data self .left = None self .right = None # function to find left most node in a tree def leftMostNode(node): while (node ! = None and node.left ! = None ): node = node.left return node # function to find right most node in a tree def rightMostNode(node): while (node ! = None and node.right ! = None ): node = node.right return node # recursive function to find the Inorder Scuccessor # when the right child of node x is None def findInorderRecursive(root, x ): if ( not root): return None if (root = = x or (findInorderRecursive(root.left, x)) or (findInorderRecursive(root.right, x))): if findInorderRecursive(root.right, x): temp = findInorderRecursive(root.right, x) else : temp = findInorderRecursive(root.left, x) if (temp): if (root.left = = temp): print ( "Inorder Successor of" , x.data, end = "") print ( " is" , root.data) return None return root return None # function to find inorder successor # of a node def inorderSuccesor(root, x): # Case1: If right child is not None if (x.right ! = None ) : inorderSucc = leftMostNode(x.right) print ( "Inorder Successor of" , x.data, "is" , end = " " ) print (inorderSucc.data) # Case2: If right child is None if (x.right = = None ): f = 0 rightMost = rightMostNode(root) # case3: If x is the right most node if (rightMost = = x): print ( "No inorder successor!" , "Right most node." ) else : findInorderRecursive(root, x) # Driver Code if __name__ = = '__main__' : 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) # This code is contributed # by SHUBHAMSINGH10 |
C#
// C# program to find inorder // successor of a node using System; class GFG { // A Binary Tree Node public class Node { public int data; public Node left, right; } // Temporary node for case 2 public static Node temp = new Node(); // Utility function to create // a new tree node public static 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 public static Node leftMostNode(Node node) { while (node != null && node.left != null ) { node = node.left; } return node; } // function to find right most // node in a tree public static 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 public static Node findInorderRecursive(Node root, Node x) { if (root == null ) { return null ; } if (root == x || (temp = findInorderRecursive(root.left, x)) != null || (temp = findInorderRecursive(root.right, x)) != null ) { if (temp != null ) { if (root.left == temp) { Console.Write( "Inorder Successor of " + x.data); Console.Write( " is " + root.data + "
" ); return null ; } } return root; } return null ; } // function to find inorder successor // of a node public static void inorderSuccesor(Node root, Node x) { // Case1: If right child is not null if (x.right != null ) { Node inorderSucc = leftMostNode(x.right); Console.Write( "Inorder Successor of " + x.data + " is " ); Console.Write(inorderSucc.data + "
" ); } // 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) { Console.Write( "No inorder successor! " + "Right most node.
" ); } else { findInorderRecursive(root, x); } } } // Driver Code public static void Main( string [] args) { // Let's con 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); } } // This code is contributed by Shrikant13 |
Output:
Inorder Successor of 3 is 6 Inorder Successor of 4 is 2 No inorder successor! Right most node.
Another approach:
We will do a reverse inorder traversal and keep the track of current visited node. Once we found the element, last tracked element would be our answer.
Below is the implementation of above approach:
Java
// Java program to find inorder successor of a node. class Node { int data; Node left, right; Node( int data) { this .data = data; left = null ; right = null ; } } // class to find inorder successor of // a node class InorderSuccessor { Node root; // to change previous node static class PreviousNode { Node pNode; PreviousNode() { pNode = null ; } } // function to find inorder successor of // a node private void inOrderSuccessorOfBinaryTree(Node root, PreviousNode pre, int searchNode) { // Case1: If right child is not NULL if (root.right != null ) inOrderSuccessorOfBinaryTree(root.right, pre, searchNode); // Case2: If root data is equal to search node if (root.data == searchNode) System.out.println( "inorder successor of " + searchNode + " is: " + (pre.pNode != null ? pre.pNode.data : "null" )); pre.pNode = root; if (root.left != null ) inOrderSuccessorOfBinaryTree(root.left, pre, searchNode); } // Driver program to test above functions public static void main(String[] args) { InorderSuccessor tree = new InorderSuccessor(); // Let's construct the binary tree // as shown in above diagram tree.root = new Node( 1 ); tree.root.left = new Node( 2 ); tree.root.right = new Node( 3 ); tree.root.left.left = new Node( 4 ); tree.root.left.right = new Node( 5 ); tree.root.right.right = new Node( 6 ); // Case 1 tree.inOrderSuccessorOfBinaryTree(tree.root, new PreviousNode(), 3 ); // Case 2 tree.inOrderSuccessorOfBinaryTree(tree.root, new PreviousNode(), 4 ); // Case 3 tree.inOrderSuccessorOfBinaryTree(tree.root, new PreviousNode(), 6 ); } } // This code is contributed by Ashish Goyal. |
C#
// C# program to find inorder successor of a node. using System; class Node { public int data; public Node left, right; public Node( int data) { this .data = data; left = null ; right = null ; } } // class to find inorder successor of // a node public class InorderSuccessor { Node root; // to change previous node class PreviousNode { public Node pNode; public PreviousNode() { pNode = null ; } } // function to find inorder successor of // a node private void inOrderSuccessorOfBinaryTree(Node root, PreviousNode pre, int searchNode) { // Case1: If right child is not NULL if (root.right != null ) inOrderSuccessorOfBinaryTree(root.right, pre, searchNode); // Case2: If root data is equal to search node if (root.data == searchNode) { Console.Write( "inorder successor of " + searchNode + " is: " ); if (pre.pNode != null ) Console.WriteLine(pre.pNode.data); else Console.WriteLine( "null" ); } pre.pNode = root; if (root.left != null ) inOrderSuccessorOfBinaryTree(root.left, pre, searchNode); } // Driver code public static void Main(String[] args) { InorderSuccessor tree = new InorderSuccessor(); // Let's construct the binary tree // as shown in above diagram tree.root = new Node(1); tree.root.left = new Node(2); tree.root.right = new Node(3); tree.root.left.left = new Node(4); tree.root.left.right = new Node(5); tree.root.right.right = new Node(6); // Case 1 tree.inOrderSuccessorOfBinaryTree(tree.root, new PreviousNode(), 3); // Case 2 tree.inOrderSuccessorOfBinaryTree(tree.root, new PreviousNode(), 4); // Case 3 tree.inOrderSuccessorOfBinaryTree(tree.root, new PreviousNode(), 6); } } // This code is contributed by PrinciRaj1992 |
Output:
inorder successor of 3 is: 6 inorder successor of 4 is: 2 inorder successor of 6 is: null
Please write comments if you find anything incorrect, or you want to share more information about the topic discussed above.
leave a comment
0 Comments