Tuesday, July 16, 2019

Inorder Successor in Binary Search Tree

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:

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;
        }
    }