Algorithms – Inorder Successor in Binary Search Tree Using Parent link
Objective: Given a Binary Search tree in which every node has a link to its parent, 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
Similar Problems :
Inorder Successor in Binary Search Tree without parent link
Inorder Successor in Binary Tree
Input: A binary search tree with nodes liked to its parents, a node x
Output: The inorder successor of node x.
Example:
Approach:
Time Complexity : O(h) , h – height of the tree
There will be 3 cases to solve this problem
Say the node for whose inorder successor needs to be find is x.
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 2: If the x doesn’t have a right child then its inorder successor will the one of its ancestors, using parent link keep traveling up till you get the node which is the left child of its parent. Then this parent node will be the inorder successor.
Case 3: if x is the right most node in the tree then its inorder successor will be NULL.
Complete Code:
| public class InOrderSuccessorWithParentPointer { | |
| public Node findInOrderSuccessor(Node root, Node x){ | |
| //if the right child of x is not null then in-Order successor will the left most node in | |
| //the right sub tree of x. | |
| if(x.right!=null){ | |
| return leftMostNode(x.right); | |
| } | |
| Node parent = x.parent; | |
| while(parent!=null && x==parent.right){ | |
| x = parent; | |
| parent = parent.parent; | |
| } | |
| return parent; | |
| } | |
| public Node leftMostNode(Node x){ | |
| while(x.left!=null){ | |
| x = x.left; | |
| } | |
| return x; | |
| } | |
| public void display(Node root){ | |
| if(root!=null){ | |
| display(root.left); | |
| System.out.print(" " + root.data); | |
| display(root.right); | |
| } | |
| } | |
| public static void main(String args[]){ | |
| Node root = new Node(10); | |
| root.left = new Node(5); | |
| root.left.parent = root; | |
| root.right = new Node(15); | |
| root.right.parent = root; | |
| root.left.left = new Node(3); | |
| root.left.left.parent = root.left; | |
| root.right.left = new Node(17); | |
| root.right.left.parent = root.right; | |
| Node a = new Node(7); | |
| root.left.right = a; | |
| root.left.right.parent = root.left; | |
| InOrderSuccessorWithParentPointer b = new InOrderSuccessorWithParentPointer(); | |
| System.out.print(" Tree : "); | |
| b.display(root); | |
| System.out.println(); | |
| Node x = b.findInOrderSuccessor(root, a); | |
| if(x!=null){ | |
| System.out.println("InOrder Successor of " + a.data + " is " + x.data); | |
| }else{ | |
| System.out.println("InOrder Successor of " + a.data + " is NULL"); | |
| } | |
| x = b.findInOrderSuccessor(root, root); | |
| if(x!=null){ | |
| System.out.println("InOrder Successor of " + root.data + " is " + x.data); | |
| }else{ | |
| System.out.println("InOrder Successor of " + root.data + " is NULL"); | |
| } | |
| } | |
| } | |
| class Node{ | |
| int data; | |
| Node left; | |
| Node right; | |
| Node parent; | |
| public Node(int data){ | |
| this.data = data; | |
| this.left = null; | |
| this.right = null; | |
| this.parent = null; | |
| } | |
| } |
Output:
Tree : 3 5 7 10 17 15 InOrder Successor of 7 is 10 InOrder Successor of 10 is 17