TRINARY TREE INSERTION AND DELETION

TRINARY TREE INSERTION AND DELETION

namespace TrinaryTree
{
    class Node
    {
        public int Data { get; set; }
        public Node Left { get; set; }
        public Node Middle { get; set; }
        public Node Right { get; set; }

        public Node(int val)
        {
            Data = val;
            Left = null;
            Right = null;
        }
    }

    class TrinaryTree
    {
        private Node root;

        public TrinaryTree()
        {
            root = null;
        }

        public void Insert(int val)
        {
            Node temp = new Node(val);

            if (root == null)
            {
                root = temp;
                return;
            }

            Node current = root;
            Node prev = null;

            while (current != null)
            {
                prev = current;

                if (val > current.Data) current = current.Right;
                else if (val < current.Data) current = current.Left;
                else current = current.Middle;
            }
            if (val > prev.Data) prev.Right = temp;
            else if (val < prev.Data) prev.Left = temp;
            else prev.Middle = temp;
        }

        public Boolean Delete(int value)
        {
            if (root == null) return false;

            Node current = root;
            Node Parent = null;

            while (current != null)         //Move to the node to be deleted
            {
                if (value > current.Data)
                {
                    Parent = current;
                    current = current.Right;
                }
                else if (value < current.Data)
                {
                    Parent = current;
                    current = current.Left;
                }
                else break;
            }

            if (current == null) return false;
            
            //Check if the val to be deleted occurs more 
            //than once , then delete the bottom most occurence of it
            if (current.Middle != null)             
            {                                       //and return
                while (current.Middle != null)
                {
                    Parent = current;
                    current = current.Middle;
                }
                Parent.Middle = null;
                return true;
            }
            
            // If the node to be deleted is the leaf node.
            if (current.Left == null && current.Right == null)   
            {
                if (current == root)
                {
                    root = null;
                }
                else if (Parent.Left == current) Parent.Left = null;
                else Parent.Right = null;
                return true;
            }

            //If the node to be deleted has only one child
            if (current.Left == null)       
            {
                if (current == root)
                {
                    root = current.Right;
                }
                else if (Parent.Left == current) Parent.Left = current.Right;
                else Parent.Right = current.Right;
            }
            else if (current.Right == null)
            {
                if (current == root)
                {
                    root = current.Left;
                }
                else if (Parent.Left == current) Parent.Left = current.Left;
                else Parent.Right = current.Left;
            }
            else  // If it has both left and right children.
            {
                Node ParentofSuccessor = null;
                Node Successor = GetSuccessor(current.Right, ref ParentofSuccessor);

                if (ParentofSuccessor == null)
                {
                    current.Data = Successor.Data;
                    current.Right = Successor.Right;
                }
                else
                {
                    current.Data = Successor.Data;
                    ParentofSuccessor.Left = Successor.Right;
                }
            }
            return true;
        }

        Node GetSuccessor(Node Node, ref Node Parent)
        {
            if (Node == null)
            {
                Parent = null;
                return null;
            }

            Parent = null;

            while (Node.Left != null)
            {
                Parent = Node;
                Node = Node.Left;
            }

            return Node;
        }
    }

    class Program
    {
        static void Main(string[] args)
        {
            TrinaryTree tree = new TrinaryTree();
            tree.Insert(5);
            tree.Insert(4);
            tree.Insert(9);
            tree.Insert(5);
            tree.Insert(7);
            tree.Insert(2);
            tree.Insert(2);

            tree.Delete(5);
            tree.Delete(5);
            tree.Delete(6);
            tree.Delete(4);
        }
    }
}

/*
 * Possible Test cases
 * 
 * 1) 
 * Insertion order : 5,4,9,5,7,2,2
 * Expected InOrder traversal: 2,2,4,5,5,7,9
 * 
 * 2)
 * Insertion order : 5,4,9,5,7,2,2
 * Deletion Order : 5
 * Expected InOrder traversal: 2,2,4,5,7,9
 * 
 * 3)
 * Insertion order : 5,4,9,5,7,2,2
 * Deletion Order : 5,5
 * Expected InOrder traversal: 2,2,4,7,9
 * 
 * 4)
 * Insertion order : 5,4,9,5,7,2,2
 * Deletion Order : 5,7
 * Expected InOrder traversal: 2,2,4,5,9
 */