Question

write a method in java for a binary search tree that receives a node as input and returns the successor node.

Answer 1

In a Binary search tree (BST) the successor node is the one which comes next to the given node in the Inorder traversal of the nodes of BST.

For eg, For an inorder traversal of aBST: 4-2-5-1-3-6, the successor of node 2 will be node 5.

Inorder works as: Travesing the leftmost nodes then the parent node of the left most node and then he right most node:

So, Left-Parent-Right

CODE:

public class Main
{
static class Node
{
int data;
Node left, right;
}
  

static Node temp = new Node();
  
//creating new node when called
static Node newNode(int data)
{
Node temp = new Node();
temp.data = data;
temp.left = temp.right = null;
return temp;
}

// recursive function to find the Scuccessor node
static Node recursiveSuccessor(Node root, Node x )
{
if (root==null)
return null;
  
if (root==x || (temp = recursiveSuccessor(root.left,x))!=null ||
(temp = recursiveSuccessor(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 + "\n");
return null;
}
}
  
return root;
}
  
return null;
}

static void findSuccessor(Node root, Node x)
{
// Case1: If right child is not null
if (x.right != null)
{ //finding left-most node
Node node = x.right;
while (node != null && node.left != null)
node = node.left;
Node inorderSucc = node;
System.out.print("Inorder Successor of "+x.data+" is ");
System.out.print(inorderSucc.data+"\n");
}
  
// Case2: If right child is null
if (x.right == null)
{
int f = 0;
Node node = root;
//finding right-most node
while (node != null && node.right != null)
node = node.right;
  
Node rightMost = node;
  
// case3: If x is the right most node
if (rightMost == x)
System.out.print("Right most node reached. No successor!\n");
else
recursiveSuccessor(root, x); // when the right child of node x is null
}
}
  
// Driver program to test above functions
public static void main(String args[])
{

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
findSuccessor(root, root.right);
  
// case 2
findSuccessor(root, root.left.left);
  
// case 3
findSuccessor(root, root.right.right);
  
}
}

OUTPUT: