Delete a node from a binary tree

Question

I create a binary tree, now I want to remove a node. I hope that you can provide me some input. The nodes are composed of characters instead of numbers.

using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;
using System.Threading.Tasks;

namespace BinaryTree
{
    public class BinaryTree
    {
        private BinaryTreeNode root;
        public BinaryTree()
        {
            root = null;
        }
        public void insert(char c)
        {
            addNode(c, ref root);
        }
        private void addNode(char c, ref BinaryTreeNode rptr)
        {
            if (rptr == null)
            rptr = new BinaryTreeNode(c);
            else if (rptr.left == null)
            addNode(c, ref rptr.left);
            else if (rptr.right == null)
                addNode(c, ref rptr.right);
            else
                addNode(c, ref rptr.left);
        }
        public void inOrderTraversal()
        {
            inOrderTraversalHelper(root);
        }
        private void inOrderTraversalHelper(BinaryTreeNode r)
        {
            if (r != null)
            {
                inOrderTraversalHelper(r.left);
                Console.Write("{0}   ", r.id);
                inOrderTraversalHelper(r.right);
            }
        }
        public void preOrderTraversal()
        {
            preOrderTraversalHelper(root);
        }
        private void preOrderTraversalHelper(BinaryTreeNode r)
        {
            if (r != null)
            {
                Console.Write("{0}   ", r.id);
                preOrderTraversalHelper(r.left);
                preOrderTraversalHelper(r.right);
            }
        }
        public void postOrderTraversal()
        {
            postOrderTraversalHelper(root);
        }
        private void postOrderTraversalHelper(BinaryTreeNode r)
        {
            if (r != null)
            {
                postOrderTraversalHelper(r.left);
                postOrderTraversalHelper(r.right);
                Console.Write("{0}   ", r.id);
            }
        }
        public void removeNode(char c)
        {
            deleteNode(c, ref root);
        }

        private void deleteNode(char c, ref BinaryTreeNode root)
        {
            if (root == null)
            { }
            else
            {
                if (root.left.id != c)
                {
                    deleteNode(c, ref root.left);
                }
                else if (root.right.id != c)
                {
                    deleteNode(c, ref root.right);
                }
                else if (root.left.id == c)
                {
                    root.left = root.left.left;
                }
                else if(root.right.id == c)
                {
                    root.right = root.right.right;
                }
            }

        }
    }

    public class BinaryTreeNode
    {
        public char id { get; set; }
        public BinaryTreeNode left;
        public BinaryTreeNode right;
        public BinaryTreeNode()
        {
            left = right = null;
        }
        public BinaryTreeNode(char _id)
        {
            id = _id;
            left = right = null;
        }
    }
 }

The main program is:

using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;
using System.Threading.Tasks;

namespace BinaryTree
{
    class Program
    {
        static void Main(string[] args)
        {
            BinaryTree b = new BinaryTree();
            b.insert('A');
            b.insert('B');
            b.insert('C');
            b.insert('D');
            b.insert('E');
            b.insert('G');
            b.insert('H');
            b.insert('F');
            b.insert('J');
            b.insert('K');
            b.insert('L');
            Console.WriteLine("The Inorder Traversal:\n");
            b.inOrderTraversal();
            Console.WriteLine("\n\nThe Preorder Traversal:\n");
            b.preOrderTraversal();
            Console.WriteLine("\n\nThe Postorder Traversal:\n");
            b.postOrderTraversal();
            b.removeNode('F');
            b.inOrderTraversal();
            Console.WriteLine("The Inorder Traversal after delete a node:\n");
            Console.WriteLine();
        }
    }
}

Answer 1

A few points:

1. Your code for both searching for the node to be removed and for removing it is broken. @HABO pointed out the second part of this. You need to check both halves of the tree for the node. Then, if you find it and delete it, you have to combine both its child subtrees into a new subtree which will be appended at this position. This involves something called 'rotating' the tree - you have to decide which of left and right becomes the new head of the subtree.

2. As you currently construct it, new nodes will almost always be inserted into the 'left' side of the tree. This means that your tree will be very far from being 'balanced'. In fact it will look something like a linked list, with a depth almost as big as the number of nodes in the tree. Balance is important in trees - some operations take longer, the more steps away from the root your nodes are. The better balanced the tree, the fewer steps there will be. There are various clever ways of guaranteeing that trees will be more or less balanced all the time. But if you just inserted new nodes randomly to the left or right, you would do a lot better most of the time.

3. Rather than implement each of your methods by calling a method in BinaryTree with a BinaryTreeNode ref argument, why don't you make these methods members of BinaryTreeNode? This would make the code a lot simpler. You should find that you can do nice things like check if the root is to be deleted, and if not call the same deleteNode function for both left and right. Same for traversal. If you do this right, you might only need one class instead of two.

I don't know if you are trying to solve a specific problem or just learn about data structures, but you might want to look up some literature on data structures and the standard ways of doing insertions, searches, etc. for various types of tree and other structure. If you can, find a book that is specific to C# or Java. Older books for C++ or other languages often have to use more complicated ways of expressing the structures based on pointers. If you learn to do this stuff nicely with a language like C# you will avoid doing things like passing ref arguments in and out when it's not strictly needed.