Below is the code for "Inorder Successor in Binary Search Tree"
Question from GeeksForGeeks: https://www.geeksforgeeks.org/inorder-successor-in-binary-search-tree/
Iterative approach:
Question from GeeksForGeeks: https://www.geeksforgeeks.org/inorder-successor-in-binary-search-tree/
Iterative approach:
public class BinarySearchTree
{
public Node root;
public int FindNextSuccessor(int key)
{
if (root == null)
return -1;
Node current = root;
int potentialSuccessor = -1;
while (current != null)
{
if (current.key == key)
{
if (current.right == null) //If there is no right then it will be potential sucessor
return potentialSuccessor;
else
return this.GetMinValue(current.right);
}
else if (key < current.key) // key will in left sub-tree
{
potentialSuccessor = current.key;
current = current.left;
}
else // key will be right sub-tree
{
//potentialSuccessor = potentialSuccessor; It will be the parent successor value
current = current.right;
}
}
return -1; // Key does't exist
}
private int GetMinValue(Node node)
{
if (node == null)
return -1; ;
Node current = node;
while (current.left != null)
{
current = current.left;
}
return current.key;
}
}
Recursion approach:
public class BinarySearchTree_Recursion
{
public Node root;
public int FindNextSuccessor(int key)
{
if (root == null)
return -1;
return this.FindNextSuccessorRec(key, this.root, -1);//Roots potentialSuccessor is -1 if right is null.
}
private int FindNextSuccessorRec(int key, Node node, int potentialSuccessor)
{
if (node == null)
return -1;
if (node.key == key)
{
if (node.right == null) //If there is no right then it will be potential sucessor
return potentialSuccessor;
else
return this.GetMinValueRec(node.right);
}
else if (key < node.key)
{
return this.FindNextSuccessorRec(key, node.left, node.key);
}
else
{
return this.FindNextSuccessorRec(key, node.right, potentialSuccessor);
}
}
private int GetMinValueRec(Node node)
{
if (node == null)
return -1;
if (node.left == null)
return node.key;
else
return this.GetMinValueRec(node.left);
}
}
Driver program:
static void Main(string[] args)
{
BinarySearchTree bst = new BinarySearchTree();
bst.root = new Node(10);
bst.root.left = new Node(6);
bst.root.left.left = new Node(4);
bst.root.left.left.left = new Node(3);
bst.root.left.left.right = new Node(5);
bst.root.left.right = new Node(8);
bst.root.left.right.left = new Node(7);
bst.root.left.right.right = new Node(9);
bst.root.right = new Node(12);
bst.root.right.left = new Node(11);
bst.root.right.right = new Node(13);
bst.root.right.right.right = new Node(14);
bst.root.right.right.right.right = new Node(18);
bst.root.right.right.right.right.left = new Node(16);
bst.root.right.right.right.right.right = new Node(21);
bst.root.right.right.right.right.left.left = new Node(15);
bst.root.right.right.right.right.left.right = new Node(17);
// 10
// / \
// 6 12
// / \ / \
// 4 8 11 13
// / \ / \ \
// 3 5 7 9 14
// \
// 18
// / \
// 16 21
// / \
// 15 17
var data10 = bst.FindNextSuccessor(10);
var data8 = bst.FindNextSuccessor(8);
var data9 = bst.FindNextSuccessor(9);
var data4 = bst.FindNextSuccessor(4);
var data11 = bst.FindNextSuccessor(11);
var data14 = bst.FindNextSuccessor(14);
var data15 = bst.FindNextSuccessor(15);
var data16 = bst.FindNextSuccessor(16);
var data17 = bst.FindNextSuccessor(17);
var data18 = bst.FindNextSuccessor(18);
var data21 = bst.FindNextSuccessor(21);
var data22 = bst.FindNextSuccessor(22);
Console.WriteLine("Successor of 10 -->; " + data10);
Console.WriteLine("Successor of 8 -->; " + data8);
Console.WriteLine("Successor of 9 -->; " + data9);
Console.WriteLine("Successor of 4 -->; " + data4);
Console.WriteLine("Successor of 11 -->; " + data11);
Console.WriteLine("Successor of 14 -->; " + data14);
Console.WriteLine("Successor of 15 -->; " + data15);
Console.WriteLine("Successor of 16 -->; " + data16);
Console.WriteLine("Successor of 17 -->; " + data17);
Console.WriteLine("Successor of 18 -->; " + data18);
Console.WriteLine("Successor of 21 -->; " + data21);
Console.WriteLine("Successor of 22 -->; " + data22);
}
public class Node
{
public int key;
public Node left;
public Node right;
public Node(int _key)
{
key = _key;
left = right = null;
}
}
