The Ins and Outs of a Binary Search Tree

In my last post we discussed the basics of tree data structures and more specifically, binary trees. Now that we have a basic understanding of how binary search trees are structured and why you would use a binary search tree, I wanted to demonstrate how you would search, insert, and delete from a binary search tree.

Search for a Node

Searching for a node is relatively easy. Remember the basic rules of a binary search tree.

1. Each node can have a left and a right child.
2. The key of the left node is less than the key then the right node.
3. No node can have the same key.

Following these three rules, start at the root node. Check to see if that node’s key is what you are looking for. If so, you have found your node. If the key is less than the current node, you then move to the left node. If the key is greater than the current node, you then move to the right node. Using this logic in a recursive manor, you will march you down the nodes of the tree until you find the node. If you don’t find the key, then the node doesn’t exist in the tree.

private Node Search(ref Node node, string key)
{
    if (node == null)
        return null;
    int val = string.Compare(key, node.Key);

    if (val == 0)
        return node;
    if (val < 0)
    {
        Node left = node.Left;
        return Search(ref left, key); // recursive search of left side
    }
    else
    {
        Node right = node.Right;
        return Search(ref right, key); // recursive search of right side
    }
}

Insert a Node

When inserting a node, the goal is to insert the node in a location that will maintain the integrity of the tree so that all rules of the binary search tree are still valid. To do this, you follow the same logic as you would for searching for a node and then you insert the new node as a leaf of the final node.

private void Insert(Node node, ref Node tree)
{
    if (tree == null) // Found a leaf?
    {
        // Found it! Add the new node as the new leaf.
        tree = node;
    }
    else
    {
        int val = string.Compare(node.Key, tree.Key);
        // already inserted
        if (val == 0)
            throw new InvalidOperationException("Duplicate key");
        if (val < 0)
        {
            Node left = tree.Left;
            Insert(node, ref left); // Keep moving down the left side.
            tree.Left = left;
        }
        else
        {
            Node right = tree.Right;
            Insert(node, ref right); // Keep moving down the right side.
            tree.Right = right;
        }
    }
}

Delete a Node

Deleting a node is the most complicated operation that you’ll perform against a binary search tree. Commonly some may think that when you are deleting a node, you’d also want to delete it’s children as well. If this was hierarchical data, that might make sense. Data within binary search tree is really just a collection of linear data though with no real hierarchical means. It’s simply stored in this form for quicker searching. With that in mind, the goal is to delete the target node and restructure any of it’s children while maintaining the integrity of the tree.

As you can probably imagine, there are three possible scenarios when deleting node.

1. Deleting a leaf node; a node with no children.
   
2. Deleting a node with a single child node.
   
3. Deleting a node with two children.

The first scenario is the easiest. Once you have found the leaf node using the same traversal logic mentioned above, you simply delete the node.

The second scenario adds a small wrinkle to the mix but is still pretty simple. You want to delete the target node and replace it with it’s single child node.

The third and final scenario is the most complicated. After you find the node you want to delete, you’ll need to find it’s successor. With binary trees, a node’s successor is the farthest left node on the right side. Then replace the deleted node with it’s successor. If the successor has a right child, it will take the place of the successor. The image below demonstrates how this would be done when deleting the root node ‘David’.  ‘Judy’ is the successor of ‘David’ as it is the left-most node on the right side. Notice that when ‘David’ is deleted and ‘Judy’ is moved into it’s place, the rules of a binary search tree are still kept in tact.

The full binary search tree implementation below shows how a deletion is done programmatically.

Full C# Implementation

Below I’ve created a generic binary search tree implementation in C#. I hope this helps bring more clarity to how a binary search tree is implemented and how one is used. While this is done in C# the same concepts apply across all languages. Each of these operations can make for great interview questions.

using System;
namespace Basics
{
    public class BinarySearchTree<T>
    {
        private class Node
        {
            public string Key { get; set; }
            public T Value { get; set; }
            public Node Left { get; set; }
            public Node Right { get; set; }
        }
        private Node _Root;
        public BinarySearchTree()
        { }
        public void Clear()
        {
            Clear(ref _Root);
        }
        private void Clear(ref Node node)
        {
            if (node != null)
            {
                Node left = node.Left;
                Clear(ref left); // recursively clear left side.
                Node right = node.Right;
                Clear(ref right); // recursively clear right side.
                node = null;
            }
        }
        public void Insert(string key, T value)
        {
            Node newNode = new Node()
            {
                Key = key,
                Value = value
            };
            if (_Root == null)
                _Root = newNode;
            else
                Insert(newNode, ref _Root);
        }
        private void Insert(Node node, ref Node tree)
        {
            if (tree == null) // Found a leaf?
            {
                // Found it! Add the new node as the new leaf.
                tree = node;
            }
            else
            {
                int val = string.Compare(node.Key, tree.Key);
                // already inserted
                if (val == 0)
                    throw new InvalidOperationException("Duplicate key");
                if (val < 0)
                {
                    Node left = tree.Left;
                    Insert(node, ref left); // Keep moving down the left side.
                    tree.Left = left;
                }
                else
                {
                    Node right = tree.Right;
                    Insert(node, ref right); // Keep moving down the right side.
                    tree.Right = right;
                }
            }
        }
        public T Search(string key)
        {
            // Search starting with the root and move down the tree as needed.
            Node node = Search(ref _Root, key);
            if (node != null)
                return node.Value;
            return default(T);
        }
        private Node Search(ref Node node, string key)
        {
            if (node == null)
                return null;

            int val = string.Compare(key, node.Key);

            if (val == 0)
                return node;

            if (val < 0)
            {
                Node left = node.Left;
                return Search(ref left, key); // recursive search of left side
            }
            else
            {
                Node right = node.Right;
                return Search(ref right, key); // recursive search of right side
            }
        }
        public void Delete(string key)
        {
            Node parent = null;
            Node nodeToDelete = FindParent(key, ref parent);
            if (nodeToDelete == null)
                throw new ArgumentNullException("Cannot find key.");
            if (nodeToDelete.Left == null && nodeToDelete.Right == null) // Simply set to null.
            {
                if (parent != null)
                {
                    if (parent.Left == nodeToDelete)
                        parent.Left = null;
                    else
                        parent.Right = null;
                }
                else
                    _Root = null;
            }
            else if (nodeToDelete.Left == null) // Left is null. Delete the node and move the child up
            {
                if (parent != null)
                {
                    if (parent.Left == nodeToDelete)
                        parent.Right = nodeToDelete.Right;
                    else
                        parent.Left = nodeToDelete.Right;

                    nodeToDelete = null;
                }
                else
                    _Root = nodeToDelete.Right;
            }
            else if (nodeToDelete.Right == null) // Right is null. Delete the node and move the child up
            {
                if (parent != null)
                {
                    if (parent.Left == nodeToDelete)
                        parent.Left = nodeToDelete.Left;
                    else
                        parent.Right = nodeToDelete.Left;
                    nodeToDelete = null;
                }
                else
                    _Root = nodeToDelete.Left;
            }
            else // Both children have nodes.
            {
                // Find the successor and replace deleted node with successor and remove successor
                Node successor = FindSuccessor(nodeToDelete, ref parent);
               // Make a copy of the successor node
                Node tmp = new Node()
                {
                    Key = successor.Key,
                    Value = successor.Value
                };
                // Find out which side the successor parent is pointing to the successor and remove the successor
                if (parent.Left == successor)
                {
                    parent.Left = successor.Right;
                }
                else
                {
                    parent.Right = successor.Left;
                }
                // Copy values to the deleted node position
                nodeToDelete.Key = tmp.Key;
                nodeToDelete.Value = tmp.Value;
            }
        }
        private Node FindParent(string key, ref Node parent)
        {
            Node node = _Root;
            parent = null;

            int val;
            while (node != null)
            {
                val = string.Compare(key, node.Key);
                if (val == 0)
                    return node;
                if (val < 0)
                {
                    parent = node;
                    node = node.Left;
                }
                else
                {
                    parent = node;
                    node = node.Right;
                }
            }

            return null;
        }
        private Node FindSuccessor(Node startNode, ref Node parent)
        {
            parent = startNode;
            startNode = startNode.Right;
            // Look for the left-most node on the right side
            while (startNode.Left != null)
            {
                parent = startNode;
                startNode = startNode.Left;
            }

            return startNode;
        }

    }
}