Click here to Skip to main content
Click here to Skip to main content
Add your own
alternative version
Go to top

Balanced Binary Search Tree (BST) (Search, Delete, InOrder, PreOrder, PostOrder,DepthFirst, BreadthFirst, BalanceTree)

, 9 Jun 2012
Balanced Binary Search Tree (BST) (Search, Delete, PrintInOrder, PrintPreOrder, PrintPostOrder,DepthFirst, BreadthFirst, BalanceTree)
BinarySearchTree.zip
BinaryTreeTester
BinaryTreeTester.4.1.resharper.user
BinaryTreeTester.suo
BinaryTreeTester
Properties
DataStructures
Properties
using System;
using System.Collections.Generic;

namespace DataStructures
{
    [Serializable]
    public class BinaryTree<T> where T : IComparable<T>
    {
        private BinaryTreeNode<T> root;
        public int Count;

        public void Insert(T value)
        {
            BinaryTreeNode<T> node = new BinaryTreeNode<T>(value);

            Insert(node);
        }

        public void Insert(BinaryTreeNode<T> node)
        {
            if (node == null)
            {
                throw new ArgumentNullException("node", "node cannot be null");
            }

            if (root == null)
            {
                root = node;
            }
            else
            {
                Insert(node, ref root);
            }

            Count++;
        }

        public void Delete(T value, bool rebalanceTree)
        {
            BinaryTreeNode<T> parentNode;
            BinaryTreeNode<T> foundNode = null;
            BinaryTreeNode<T> tree = parentNode = root;

            //Search for the node while keeping a reference to the parent
            while (tree != null)
            {
                if (value.CompareTo(tree.Data) == 0)
                {
                    foundNode = tree;
                    break;
                }
                else if (value.CompareTo(tree.Data) < 0)
                {
                    parentNode = tree;
                    tree = tree.Left;
                }
                else if (value.CompareTo(tree.Data) > 0)
                {
                    parentNode = tree;
                    tree = tree.Right;
                }
            }

            if (foundNode == null)
            {
                throw new Exception("Node not found in binary tree");
            }


            bool leftOrRightNode = false;

            if (foundNode != parentNode.Left)
            {
                leftOrRightNode = true;
            }

            if (foundNode == parentNode) //oh oh. We're trying to delete the root here.
            {
                if (rebalanceTree)
                {
                    //Let's just remove the parent and rebalance the tree to ensure our tree will be nice and balanced
                    //after the removal
                    IList<BinaryTreeNode<T>> listOfNodes = new List<BinaryTreeNode<T>>();

                    FillListInOrder(root, listOfNodes);
                    RemoveChildren(listOfNodes);
                    listOfNodes.Remove(parentNode);

                    root = null;
                    int count = Count - 1;
                    Count = 0;

                    BalanceTree(0, count - 1, listOfNodes);
                }
                else
                {
                    BinaryTreeNode<T> leftMost = FindLeftMost(parentNode.Right, true);

                    if (leftMost != null)
                    {
                        leftMost.Left = parentNode.Left;
                        leftMost.Right = parentNode.Right;
                        root = leftMost;
                    }
                }
            }
            else if (foundNode.Left == null && foundNode.Right == null) //This is a leaf node
            {
                //Just set it to null
                if (leftOrRightNode)
                {
                    parentNode.Right = null;
                }
                else
                {
                    parentNode.Left = null;
                }
            }
            else if (foundNode.Left != null && foundNode.Right != null) //This is a node with two children
            {
                if (leftOrRightNode)
                {
                    parentNode.Right = foundNode.Right;
                    parentNode.Right.Left = foundNode.Left;
                }
                else
                {
                    parentNode.Left = foundNode.Right;
                    parentNode.Left.Left = foundNode.Left;
                }
            }

            else if (foundNode.Left != null || foundNode.Right != null) //This is a node with a single child
            {
                if (foundNode.Left != null)
                {
                    if (leftOrRightNode)
                    {
                        parentNode.Right = foundNode.Left;
                    }
                    else
                    {
                        parentNode.Left = foundNode.Left;
                    }
                }
                else
                {
                    if (leftOrRightNode)
                    {
                        parentNode.Right = foundNode.Right;
                    }
                    else
                    {
                        parentNode.Left = foundNode.Right;
                    }
                }
            }
        }

        private BinaryTreeNode<T> FindLeftMost(BinaryTreeNode<T> node, bool setParentToNull)
        {
            BinaryTreeNode<T> leftMost = null;
            BinaryTreeNode<T> current = leftMost = node;
            BinaryTreeNode<T> parent = null;

            while (current != null)
            {
                if (current.Left!=null)
                {
                    parent = current;
                    leftMost = current.Left;
                }
            
                current = current.Left;
            }

            if (parent!=null && setParentToNull)
            {
                parent.Left = null;
            }

            return leftMost;
        }

        public BinaryTreeNode<T> Search(T value)
        {
            BinaryTreeNode<T> tree = root;

            while (tree != null)
            {
                if (value.CompareTo(tree.Data) == 0)
                {
                    return tree;
                }
                else if (value.CompareTo(tree.Data) < 0)
                {
                    tree = tree.Left;
                }
                else if (value.CompareTo(tree.Data) > 0)
                {
                    tree = tree.Right;
                }
            }

            return null;
        }

        public IEnumerable<BinaryTreeNode<T>> InOrder()
        {
            return InOrder(root);
        }

        private IEnumerable<BinaryTreeNode<T>> InOrder(BinaryTreeNode<T> node)
        {
            if (node != null)
            {
                foreach (BinaryTreeNode<T> left in InOrder(node.Left))
                {
                    yield return left;
                }

                yield return node;

                foreach (BinaryTreeNode<T> right in InOrder(node.Right))
                {
                    yield return right;
                }
            }
        }

        public IEnumerable<BinaryTreeNode<T>> PreOrder()
        {
            return PreOrder(root);
        }

        public IEnumerable<BinaryTreeNode<T>> PostOrder()
        {
            return PostOrder(root);
        }

        public IEnumerable<BinaryTreeNode<T>> BreadthFirstTraversal()
        {
            Queue<BinaryTreeNode<T>> queue = new Queue<BinaryTreeNode<T>>();

            queue.Enqueue(root);

            while (queue.Count != 0)
            {
                BinaryTreeNode<T> current = queue.Dequeue();

                if (current != null)
                {
                    queue.Enqueue(current.Left);
                    queue.Enqueue(current.Right);

                    yield return current;
                }
            }
        }

        public IEnumerable<BinaryTreeNode<T>> DepthFirstTraversal()
        {
            Stack<BinaryTreeNode<T>> queue = new Stack<BinaryTreeNode<T>>();

            BinaryTreeNode<T> current;

            queue.Push(root);

            while (queue.Count != 0)
            {
                current = queue.Pop();

                if (current != null)
                {
                    queue.Push(current.Right);
                    queue.Push(current.Left);

                    yield return current;
                }
            }
        }

        public void BalanceTree()
        {
            IList<BinaryTreeNode<T>> listOfNodes = new List<BinaryTreeNode<T>>();

            FillListInOrder(root, listOfNodes);
            RemoveChildren(listOfNodes);

            root = null;
            int count = Count;
            Count = 0;

            BalanceTree(0, count - 1, listOfNodes);
        }

        private void Insert(BinaryTreeNode<T> node, ref BinaryTreeNode<T> parent)
        {
            if (parent == null)
            {
                parent = node;
            }
            else
            {
                if (node.Data.CompareTo(parent.Data) < 0)
                {
                    Insert(node, ref parent.Left);
                }
                else if (node.Data.CompareTo(parent.Data) > 0)
                {
                    Insert(node, ref  parent.Right);
                }
                else if (node.Data.CompareTo(parent.Data) == 0)
                {
                    throw new ArgumentException("Duplicate node");
                }
            }
        }

        private void BalanceTree(int min, int max, IList<BinaryTreeNode<T>> list)
        {
            if (min <= max)
            {
                int middleNode = (int)Math.Ceiling(((double)min + max) / 2);

                Insert(list[middleNode]);

                BalanceTree(min, middleNode - 1, list);

                BalanceTree(middleNode + 1, max, list);
            }
        }

        private void FillListInOrder(BinaryTreeNode<T> node, ICollection<BinaryTreeNode<T>> list)
        {
            if (node != null)
            {
                FillListInOrder(node.Left, list);

                list.Add(node);

                FillListInOrder(node.Right, list);
            }
        }

        private void RemoveChildren(IEnumerable<BinaryTreeNode<T>> list)
        {
            foreach (BinaryTreeNode<T> node in list)
            {
                node.Left = null;
                node.Right = null;
            }
        }

        private IEnumerable<BinaryTreeNode<T>> PreOrder(BinaryTreeNode<T> node)
        {
            if (node != null)
            {
                yield return node;

                foreach (BinaryTreeNode<T> left in PreOrder(node.Left))
                {
                    yield return left;
                }

                foreach (BinaryTreeNode<T> right in PreOrder(node.Right))
                {
                    yield return right;
                }
            }
        }

        private IEnumerable<BinaryTreeNode<T>> PostOrder(BinaryTreeNode<T> node)
        {
            if (node != null)
            {
                foreach (BinaryTreeNode<T> left in PostOrder(node.Left))
                {
                    yield return left;
                }

                foreach (BinaryTreeNode<T> right in PostOrder(node.Right))
                {
                    yield return right;
                }

                yield return node;
            }
        }
    }

    [Serializable]
    public class BinaryTreeNode<T> where T : IComparable<T>
    {
        public BinaryTreeNode(T value)
        {
            Data = value;
        }

        public T Data
        {
            get;
            set;
        }

        public BinaryTreeNode<T> Left;

        public BinaryTreeNode<T> Right;
    }
}

By viewing downloads associated with this article you agree to the Terms of Service and the article's licence.

If a file you wish to view isn't highlighted, and is a text file (not binary), please let us know and we'll add colourisation support for it.

License

This article, along with any associated source code and files, is licensed under The Code Project Open License (CPOL)

Share

About the Author

FatCatProgrammer
Software Developer (Senior) Finance Industry
United States United States
Currently pursuing 'Programming Nirvana' (The ineffable ultimate in which one has attained disinterested wisdom and compassion as it relates to programming)
 
Respected Technologies
1. Confusor (https://confuser.codeplex.com/)
2. Power Threading (http://www.wintellect.com/Resources/visit-the-power-threading-library)
3. EDI Parsers (http://www.rdpcrystal.com)
 

Acknowledgements:
 
Microsoft Certified Technologist for WPF and .Net 3.5 (MCTS)
Microsoft Certified Technologist for WCF and .Net 3.5 (MCTS)
Microsoft Certified Application Developer for .Net (MCAD)
Microsoft Certified Systems Engineer (MCSE)
Microsoft Certified Professional (MCP)
 
Sun Certified Developer for Java 2 Platform (SCD)
Sun Certified Programmer for Java 2 Platform (SCP)
Sun Certified Web Component Developer (SCWCD)
 
CompTIA A+ Certified Professional
 
Registered Business School Teacher for Computer Programming and Computer Applications (2004)
(University of the State of New York Education Department)
 
Graduated from University At Stony Brook

| Advertise | Privacy | Mobile
Web03 | 2.8.140916.1 | Last Updated 10 Jun 2012
Article Copyright 2010 by FatCatProgrammer
Everything else Copyright © CodeProject, 1999-2014
Terms of Service
Layout: fixed | fluid