B tree - Avinashlikes/Wiki GitHub Wiki

namespace VerticalOrderBTree { public class BST { private Node _head;

    public BST()
    {
        _head = null;
    }

    public void InsertReq(int key)
    {
        _head = InsertReq(_head, key);
    }

    public Node InsertReq(Node root, int key)
    {
        //if tree is empty return a new key in BST
        if (root == null)
        {
            root = new Node(key);
        }

        //otherwise recur down the tree
        if (key < root.key)
        {
            if (root.left == null)
            {
                root.left = new Node(key);
            }
            else
            {
                // else add it to the left node
                InsertReq(root.left, key);
            }
        }
        else if (key > root.key)
        {
            if (root.right == null)
            {
                root.right = new Node(key);
            }
            else
            {
                // else add it to the left node
                InsertReq(root.right, key);
            }

        }

        // return the (unchanged) node pointer
        return root;
    }

    //this method mainly callls InorderRec
    public void InOrder()
    {
        InOrderRec(_head);
    }
    public void InOrderRec(Node node)
    {
        if (node != null)
        {
            InOrderRec(node.left);
            System.Console.WriteLine(node.key);
            InOrderRec(node.right);
        }
    }
    public void PreOrder()
    {
        PreOrder(_head);
    }

    public void PreOrder(Node node)
    {
        if (node != null)
        {
            System.Console.WriteLine(node.key);
            PreOrder(node.left);
            PreOrder(node.right);
        }
    }

    public void PostOrder()
    {
        PostOrder(_head);
    }

    public void PostOrder(Node node)
    {
        if (node != null)
        {
            PostOrder(node.left);
            PostOrder(node.right);
            System.Console.WriteLine(node.key);
        }
    }

    public bool Remove(int key)
    {
        Node Current, Parent;
        Current = FindWithParent(key, out Parent);

        if (Current == null)
        {
            return false;
        }

        // Case 1: If current has no right child, then current's left replaces current
        if (Current.right == null)
        {
            if (Parent == null)
            {
                _head = Current.left;
            }

            else
            {
                int result = Parent.key > Current.key ? 1 : (Parent.key < Current.key ? -1 : 0);
                if (result > 0)
                {
                    // if parent value is greater than current value
                    // make the current left child a left child of parent
                    Parent.left = Current.left;
                }
                else if (result < 0)
                {
                    // if parent value is less than current value
                    // make the current left child a right child of parent
                    Parent.right = Current.left;
                }
            }
        }

        // Case 2: If current's right child has no left child, then current's right child
        //         replaces current
        else if (Current.right.left == null)
        {
            Current.right.left = Current.left;

            if (Parent == null)
            {
                _head = Current.right;
            }
            else
            {
                int result = Parent.key > Current.key ? 1 : (Parent.key < Current.key ? -1 : 0);
                if (result > 0)
                {
                    // if parent value is greater than current value
                    // make the current right child a left child of parent
                    Parent.left = Current.right;
                }
                else if (result < 0)
                {
                    // if parent value is less than current value
                    // make the current right child a right child of parent

                    Parent.right = Current.right;
                }
            }

        }

        // Case 3: If current's right child has a left child, replace current with current's
        //         right child's left-most child
        else
        {
            // find the right's left-most child

            Node leftMost = Current.right.left;
            Node leftMostParent = Current.right;

            while (leftMost.left != null)
            {
                leftMostParent = leftMost;
                leftMost = leftMost.left;
            }

            // the parent's left subtree becomes the leftmost's right subtree
            leftMostParent.left = leftMost.right;


            // assign leftmost's left and right to current's left and right children
            leftMost.left = Current.left;
            leftMost.right = Current.right;

            if (Parent == null)
            {
                _head = leftMost;
            }
            else
            {
                int result = Parent.key > Current.key ? 1 : (Parent.key < Current.key ? -1 : 0);
                if (result > 0)
                {
                    // if parent value is greater than current value
                    // make leftmost the parent's left child

                    Parent.left = leftMost;

                }
                else if (result < 0)
                {
                    // if parent value is less than current value
                    // make leftmost the parent's right child

                    Parent.right = leftMost;
                }
            }
        }
        return true;

    }

    private Node FindWithParent(int key, out Node Parent)
    {
        Node current = _head;
        Parent = null;

        while (current != null)
        {
            int result = current.key > key ? 1 : (current.key < key ? -1 : 0);
            if (result > 0)
            {
                Parent = current;
                current = current.left;

            }
            else if (result < 0)
            {
                Parent = current;
                current = current.right;

            }
            else
            {
                break;
            }
        }

        return current;
    }



    public void Add(int values)
    {
        if (_head == null)
        {
            _head = new Node(values);
        }
        else
        {
            AddTo(_head, values);
        }

    }

    public void AddTo(Node node, int values)
    {
        if (values < node.key)
        {

            if (node.left == null)
            {
                node.left = new Node(values);
            }
            else
            {
                AddTo(node.left, values);
            }

        }
        else
        {

            if (node.right == null)
            {
                node.right = new Node(values);
            }
            else
            {
                AddTo(node.right, values);
            }
        }
    }


}

}