Inorder Successor in Binary Tree | Algorithms
Objective: Given a Binary tree (Not binary Search Tree ), find the inorder successor of a node.
What is Inorder Successor: Inorder successor of a node is the next node in the inorder traversal of the tree. For the last node in a tree, inorder successor will be NULL
Case 1 : If the x has a right child then its inorder successor will the left most element in the right sub tree of x.
Case 3: if x is the right most node in the tree then its inorder successor will be NULL.
https://rajneesh2k10.wordpress.com/2011/06/25/inorder-successor/
Read full article from Inorder Successor in Binary Tree | Algorithms
Objective: Given a Binary tree (Not binary Search Tree ), find the inorder successor of a node.
What is Inorder Successor: Inorder successor of a node is the next node in the inorder traversal of the tree. For the last node in a tree, inorder successor will be NULL
Following is simple algorithm for finding Inorder Successor of binary tree.
Step 1: Current root itself is NULL, then successor is also NULL.
Step 2: Current root contains value same as key for which we are looking successor.
2.1: Current root has right child, then left most node of right child is successor.
2.2: Current root doesn't has right child, then parent of current root is successor.
Step 3: Current root is not the target node for which we are looking successor.
3.1: Search target node and its successor in left side of tree recursively, and return if found.
3.2: Search target node and its successor in right side of tree recursively, and return.
Node *inorderSuccessorRec(Node *root, int key, Node *parent) |
23 | { |
24 | //Case 1: Current root itself is NULL, then successor is also NULL. |
25 | if (root==NULL) |
26 | return 0; |
27 | //Case 2: Current root contains value same as key for which we are looking successor. |
28 | if (root->data == key) |
29 | { |
30 | //Case 2.1: Current root has right child, then left most node of right child is successor. |
31 | if (root->right) |
32 | return findLeftMostNode(root->right); |
33 | //Case 2.2: Current root doesn't has right child, then parent of current root is successor. |
34 | else |
35 | return parent; |
36 | } |
37 | //Case 3: Current root is not the target node for which we are looking successor. |
38 | else |
39 | { |
40 | //Case 3.1: Search target node and its successor in left side of tree recursively, and return if found. |
41 | Node *left=inorderSuccessorRec(root->left,key,root); |
42 | if (left) |
43 | return left; |
44 | //Case 3.2: Search target node and its successor in right side of tree recursively, and return. |
45 | return inorderSuccessorRec(root->right,key,parent); |
46 | } |
47 | } |
Case 1 : If the x has a right child then its inorder successor will the left most element in the right sub tree of x.
Case 3: if x is the right most node in the tree then its inorder successor will be NULL.
public class InOrderSuccessorBinaryTree { public static TreeNode n = null; public static Boolean nodeFound = false; public TreeNode inOrderSuccBiTree(TreeNode root, TreeNode x){ nodeFound = false; if(x.right!=null){ TreeNode temp = leftMostTreeNode(x.right); System.out.println("The In Order Successor for '" + x.data + "' is "+ temp.data ); return temp; } return findRecur(root, x); } public TreeNode findRecur(TreeNode root, TreeNode x){ if(root==null) return null; if(root==x||(n = findRecur(root.left,x))!=null||(n=findRecur(root.right,x))!=null){ if(n!=null){ if(root.left==n){ nodeFound = true; System.out.println("The In Order Successor for '" + x.data + "' is "+ root.data ); return null; } } return root; } return null; } public TreeNode leftMostTreeNode(TreeNode x){ while(x.left!=null){ x = x.left; } nodeFound = true; return x; }}https://rajneesh2k10.wordpress.com/2011/06/25/inorder-successor/
Node *findRightSuccessor(Node *root){ while (root->left) root=root->left; return root;}Node *inorderSuccessor(Node *root, int key, Node *parent){ if (root==NULL) return 0; if (root->data == key) { if (root->right) return findRightSuccessor(root->right); else return parent; } Node *left=inorderSuccessor(root->left,key,root); if (left) return left; return inorderSuccessor(root->right,key,parent);}Node *inorderSuccessor(Node *root, int key){ return inorderSuccessor(root,key,NULL);}