C# Binary Search Tree Remove

Question

I'm trying to remove items from a Binary Search Tree. I can insert numbers just fine and further working functions to find the height and size of the tree but I can't get the code removal function working.

I have figured out what I need to do merge the subtrees if necessary and set the smallest number (least item) as the new node but I'm currently unable to get it working

Thank you in advance for any help.

The code I've currently got:

Main:

static void Main(string[] args)
    {
        BSTree<int> testTree = new BSTree<int>();

        testTree.InsertItem(6);
        testTree.InsertItem(12);
        testTree.InsertItem(1);

        testTree.RemoveItem(12);
    }

BinTree:

class BinTree<T> where T : IComparable
{
    protected Node<T> root;

    public BinTree()
    {
        root = null;
    }
    public BinTree(Node<T> node)
    {
        root = node;
    }

Node:

class Node<T> where T : IComparable
{
    private T data;
    public Node<T> Left, Right;

    public Node(T item)
    {
        data = item;
        Left = null;
        Right = null;
    }
    public T Data
    {
        set { data = value; }
        get { return data; }
    }
}

BSTree:

class BSTree<T> : BinTree<T> where T:IComparable
{
    public BSTree()
    {
        root = null;
    }
    public void InsertItem(T item)
    {
        insertItem(item, ref root);
    }
    private void insertItem(T item, ref Node<T> tree)
    {
        if (tree == null)
            tree = new Node<T>(item);
        else if (item.CompareTo(tree.Data) < 0)
            insertItem(item, ref tree.Left);
        else if (item.CompareTo(tree.Data) > 0)
            insertItem(item, ref tree.Right);
    }
    public void RemoveItem(T item)
    {
        removeItem(item, ref root);
    }
    private void removeItem(T item, ref Node<T> tree)
    {
        if (tree == null)
            tree = new Node<T>(item);
        if (item.CompareTo(tree.Data) < 0)
            removeItem(item, ref tree.Left);
        else if (item.CompareTo(tree.Data) > 0)
            removeItem(item, ref tree.Right);
        if (tree.Left == null)
            tree = tree.Right;
        else if (tree.Right == null)
            tree = tree.Left;

        T newRoot = leastItem(tree.Right);
        tree.Data = newRoot;
        removeItem(newRoot, ref tree.Right);
    }
    public T leastItem(Node<T> tree) //returns left most item in tree
    {
        if (tree.Left == null) //if tree.Left is empty
            return tree.Data;
        else
        {
            return leastItem(tree.Left);
        }
    }

You can have a look at this [example](https://www.geeksforgeeks.org/binary-search-tree-set-2-delete/) — Pavel Anikhouski, Jan 11 '20 at 19:37
https://stackoverflow.com/questions/3262947/is-there-a-built-in-binary-search-tree-in-net-4-0 — Hans Passant, Jan 11 '20 at 20:09
Your binary tree lacks the reference to parent. Without that you cannot implement correct remove of item easily. — L_J, Jan 11 '20 at 20:13

score 0 · Answer 1 · answered Jan 11 '20 at 21:13

Here is a working example build on your notations.

class Program
{
    static void Main(string[] args)
    {
        BSTree<int> testTree = new BSTree<int>();

        //testTree.InsertItem(6);
        //testTree.InsertItem(12);
        //testTree.InsertItem(1);
        //testTree.Print();
        //Console.WriteLine();

        //testTree.RemoveItem(12);
        //testTree.Print();
        //Console.WriteLine();

        List<int> ls = new List<int> { 10, 5, 19, 1, 6, 17, 21, 9 };
        foreach (int i in ls)
            testTree.InsertItem(i);

        testTree.Print();
        Console.WriteLine();

        testTree.RemoveItem(6);
        testTree.Print();
        Console.WriteLine();

        Console.Read();
    }
}

class BinTree<T> where T : IComparable
{
    protected Item<T> root;

    public BinTree()
    {
        root = null;
    }
    public BinTree(Item<T> item)
    {
        root = item;
    }
}

class Item<T> where T : IComparable
{
    public Item<T> Left, Right, Parent;

    public Item(T item)
    {
        Data = item;
        Left = null;
        Right = null;
    }
    public T Data { set; get; }
}

class BSTree<T> : BinTree<T> where T : IComparable
{
    public BSTree()
    {
        root = null;
    }

    public void InsertItem(T item)
    {
        Item<T> tmp = root;
        Item<T> par = tmp;

        while (tmp != null)
        {
            par = tmp;
            if (tmp.Data.CompareTo(item) == 0)
            {
                Console.WriteLine($"Element {item} already exist\n");
                return;
            }
            else if (tmp.Data.CompareTo(item) > 0)
                tmp = tmp.Left;
            else
                tmp = tmp.Right;
        }

        tmp = new Item<T>(item);

        if (par == null)
        {
            tmp.Parent = tmp;
            root = tmp;
        }
        else
        {
            tmp.Parent = par;
            if (item.CompareTo(par.Data) < 0)
                par.Left = tmp;
            else
                par.Right = tmp;
        }
    }

    public void RemoveItem(T item)
    {
        Item<T> theItem = Find(item);
        RemoveItem(theItem);
    }

    private Item<T> Find(T value)
    {
        Item<T> tmp = root;
        while (tmp != null)
        {
            if (value.CompareTo(tmp.Data) == 0)
                return tmp;
            else if (value.CompareTo(tmp.Data) < 0)
                tmp = tmp.Left;
            else
                tmp = tmp.Right;
        }
        return null;
    }

    private void RemoveItem(Item<T> item)
    {
        if (item == null)
            return;

        if (item.Left == null && item.Right == null)
        {
            #region Remove leaf
            if (item == root)
                root = null;
            else
            {
                Item<T> par = item.Parent;
                if (par.Left == item)
                    par.Left = null;
                else
                    par.Right = null;
            }
            #endregion
        }
        else if (item.Left == null || item.Right == null)
        {
            #region Remove item with one child
            bool isroot = item == root;

            var par = item.Parent;
            var newchild = item.Left ?? item.Right;
            newchild.Parent = par;
            if (par.Left == item)
                par.Left = newchild;
            else
                par.Right = newchild;

            if (isroot)
                root = newchild;
            #endregion
        }
        else
        {
            #region Remove item with two children
            Item<T> repl = Max(item.Left);
            item.Data = repl.Data;
            RemoveItem(repl);
            #endregion
        }
    }

    private Item<T> Max(Item<T> node)
    {
        Item<T> tmp = node;
        Item<T> ret = node;
        while (tmp != null)
        {
            ret = tmp;
            tmp = tmp.Right;
        }
        return ret;
    }

    public void Print(Item<T> node = null) => _print(node ?? root);

    private void _print(Item<T> node)
    {
        if (node != null)
        {
            _print(node.Left);
            Console.Write(node.Data + " ");
            _print(node.Right);
        }
    }
}

C# Binary Search Tree Remove

1 Answers1