Firat Atagun

Below is my binary search tree implementation (Not self balancing). Binary search trees are very common data structure and being used by many algorithms. Furthermore, binary search trees can be adopted to solve many algorithms, problems and puzzles.

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

namespace FiratAtagun.DataStructures
{
    public abstract class Node :  IEquatable, IEquatable> where T : IComparable
    {
        public T Value { set; get; }

        protected Node(T value)
        {
            Value = value;
        }

        protected Node()
        {

        }

        public override string ToString()
        {
            return Value.ToString();
        }

        public override int GetHashCode()
        {
            return Value.GetHashCode();
        }

        public override bool Equals(object obj)
        {
            return base.Equals(obj);
        }

        public bool Equals(T other)
        {
            return Value.Equals(other);
        }

        public bool Equals(Node other)
        {
            return Value.Equals(other.Value);
        }

        public static bool operator <(Node left, Node right)
        {
            if(left.Value.CompareTo(right.Value) < 0)
            {
                return true;
            }

            return false;
        }

        public static bool operator >(Node left, Node right)
        {
            if (left.Value.CompareTo(right.Value) > 0)
            {
                return true;
            }

            return false;
        }

    }
}

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

namespace FiratAtagun.DataStructures
{
    public class TreeNode : Node where T : IComparable
    {

        public TreeNode LeftChild { set; get; }
        public TreeNode RightChild { set; get; }

        public TreeNode()
        {
        }

        public TreeNode(T value): base(value)
        {
        }
    }
}

using System;
using System.Collections.Generic;

namespace FiratAtagun.DataStructures
{
    public class BinaryTree : IEnumerable, IEnumerable> where T: IComparable
    {

        public TreeNode Root { set; get; }

        public BinaryTree()
        {

        }

        public BinaryTree(IEnumerable collection)
        {
            foreach (var item in collection)
            {
                Insert(item);
            }
        }

        public void Insert(T value)
        {
           Insert(new TreeNode(value));
        }

        public void Insert(TreeNode treeNode)
        {
            if (ReferenceEquals(Root, null))
            {
                Root = treeNode;
                return;
            }

            var currentNode = Root;

            var node = treeNode;

            while (true)
            {
                if (node < currentNode)
                {

                    if (ReferenceEquals(currentNode.LeftChild, null))
                    {
                        currentNode.LeftChild = node;
                        break;
                    }
                    currentNode = currentNode.LeftChild;
                    continue;
                }

                if (node > currentNode)
                {

                    if (ReferenceEquals(currentNode.RightChild, null))
                    {
                        currentNode.RightChild = node;
                        break;
                    }
                    currentNode = currentNode.RightChild;
                    continue;
                }
            }
        }

        public void InsertRecursively(T value)
        {
            var node = new TreeNode(value);

            if(ReferenceEquals(Root, null))
            {
                Root = node;
                return;
            }

            var currentNode = Root;

            InsertRecursively(currentNode, node);
        }

        public void InsertRecursively(TreeNode currentNode , TreeNode node)
        {
            if(node < currentNode)
            {
                if(ReferenceEquals(currentNode.LeftChild,null))
                {
                    currentNode.LeftChild = node;
                    return;
                }
                InsertRecursively(currentNode.LeftChild, node);
                return;
            } 

            if(node > currentNode)
            {
                if(ReferenceEquals(currentNode.RightChild, null))
                {
                    currentNode.RightChild = node;
                    return;
                }
                InsertRecursively(currentNode.RightChild, node);
                return;
            }
        }

        public int NumberOfNodes
        {
            get { return NumberOfNodesMethod(); }
        }

        private int NumberOfNodesMethod()
        {
            if(ReferenceEquals(Root,null))
            {
                return 0;
            }

            return NumberOfNodesImpl(Root);
        }

        private static int NumberOfNodesImpl(TreeNode treeNode)
        {
            if(ReferenceEquals(treeNode, null))
            {
                return 0;
            }

            var count = 1 + NumberOfNodesImpl(treeNode.LeftChild) + NumberOfNodesImpl(treeNode.RightChild);

            return count;
        }

        public int Height
        {
            get { return GetHeight() -1; }
        }

        private int GetHeight()
        {
            if(ReferenceEquals(Root, null))
            {
                return 0;
            }

            return GetHeight(Root);
        }

        private static int GetHeight(TreeNode node)
        {
            if(ReferenceEquals(node, null))
            {
                return 0;
            }

            return 1 + Math.Max(GetHeight(node.LeftChild), GetHeight(node.RightChild));
        }

        public void PreOrderTraversal()
        {
            if(ReferenceEquals(Root, null))
            {
                return;
            }

            var currentNode = Root;

            PreOrderTraversal(currentNode);
        }

        public void PreOrderTraversal(TreeNode node)
        {
            if(ReferenceEquals(node, null))
            {
                return;
            }

            Console.WriteLine(node.Value);
            PreOrderTraversal(node.LeftChild);
            PreOrderTraversal(node.RightChild);
        }

        public void InOrderTraversal()
        {
            if(ReferenceEquals(Root, null))
            {
                return;
            }

            InOrderTraversalImpl(Root);
        }

        public void InOrderTraversalImpl(TreeNode node)
        {
            if(ReferenceEquals(node, null))
            {
                return;
            }

            InOrderTraversalImpl(node.LeftChild);
            Console.WriteLine(node.Value);
            InOrderTraversalImpl(node.RightChild);
        }

        public void PostOrderTraversal()
        {
            if(ReferenceEquals(Root,null))
            {
                return;
            }

            PostOrderTraversalImpl(Root);
        }

        public void PostOrderTraversalImpl(TreeNode node)
        {
            if(ReferenceEquals(node, null))
            {
                return;
            }

            PostOrderTraversalImpl(node.LeftChild);
            PostOrderTraversalImpl(node.RightChild);
            Console.WriteLine(node.Value);
        }

        public IEnumerator GetEnumerator()
        {
            throw new NotImplementedException();
        }

        System.Collections.IEnumerator System.Collections.IEnumerable.GetEnumerator()
        {
            throw new NotImplementedException();
        }

        IEnumerator> IEnumerable>.GetEnumerator()
        {
            throw new NotImplementedException();
        }
    }
}

LinkedList is a common data structure being used. One of the difference between linked list and array based structures are, linked list doesn’t require contiguous memory space. Moreover, expansion within array based data structures bases on a load factor that s determined by the engineers who build the structures, and expansion of arrays usually twice the size of the current size. During expansion of the array, CLR creates a new array with the new size and then copy all the entities from one array to another. Even though this seems to be a an easy operation, as you data grows, it might become slow. Imagine, your array size becomes 5 million elements, next expansion would require contiguous memory to hold 10 million blocks. So this operation becomes very expensive. Benefit of linked list in the aspect is that, it doesn’t require contiguous memory space, nodes can be anywhere withing the Virtual Memory. Since we keep pointers to the nodes, that is sufficient to access any node which is linked by another node. Therefore the issue we mentioned above doesn’t happen with linked list.

There can be several algorithms and problems based on linked list due to the fact that linked list is convenient for multiple pointer usages, recursion, iteration, reversing etc.
Some of the examples are follows and the best way to practice them is to write code for it after understanding them.

If there is a cycle in a given linked list, you can find it by marking the visited nodes as visited, if you see a visited node again, you halt. This solution requires you to modify the Node structure and add a bolean to it. Another solution would be to have two pointers at the beginning, one that moves one by one node, and another pointer, that moves 2 nodes at a time. And if there is a cycle in the linked list they will meet both pointers will eventually meet.

A way to find out the middle element of a linked list is to use two pointers, one that moves one by one and another that moves two by two. Once the one that moves two nodes at a time reaches to the end, first node comes to the middle of the linked list.

To check if a given linked list is palindrome, divide the list into two parts. Reverse the first part and compare with the second part node by node. If they are equal that, linked list contains a palindrome. There are several different approaches to solve palindrome problem both recursively and iteratively.

Given two singly linked lists in sorted order, which forms a Y shape, you can reverse both of the linked lists and compare each element one by one by keeping two pointers. Once you reach the nodes that don’t intersect. Previous nodes are the intersection points.

Given a sorted singly linked, it s possible to remove the duplicates with a single iteration, by keeping two pointers, one to current node and one to the next node. If the next node is equal to current node, connect the current node to next node’s next node.

Given an unsorted singly linked list, it s possible to remove duplicates by using a dictionary. Store elements in the dictionary as you iterate the list. Each time you move to a node, check the dictionary, if the element is in the dictionary already, that s duplicate. Another way is to sort and do the above algorithm.

Given a linked list of even and odd numbers, you can separate the even numbers from the odd ones as follows. Using two pointers, one to point to the head and another to point to the tail, start iterating from both ends, if first pointer’s node is even and second pointer node is odd then swap them. Otherwise keep moving the pointers until you reach a odd or even number. Then swap them until two pointers overlap.

Given a linked list in which you need to set the last node as the head of the linked list. You traverse the linked list once. Once you reach to the end, you also keep a previous pointer to find the node that will qualify to last node. Last node next pointer will be assigned to the head pointer and then will qualify to be the head node. Tail node will be the second pointer node, whose next pointer will point to null.

Below is an implementation of a linked list that I have quickly written. Syntax hightlighter is not working perfect as you can see. Sorry about that.

using System;
using System.Collections;
using System.Collections.Generic;

namespace FiratAtagun.DataStructureTests.LinkedList
{
    public class Node : IEquatable where T : IComparable
    {
        public Node Next;

        public Node()
        {
        }

        public Node(T data)
        {
            Data = data;
        }

        public Node(Node data)
        {
            Data = data.Data;
        }

        public Node(T data, Node next)
        {
            Data = data;
            Next = next;
        }

        public T Data { set; get; }

        #region IEquatable Members

        public bool Equals(T other)
        {
            return Data.Equals(other);
        }

        #endregion
    }

    public enum InsertionMethod
    {
        Default,
        Recursive,
        Iterative
    }

    public class SinglyLinkedList : ICollection> where T : IComparable
    {
        private int _count;
        private Node _head;
        private Node _iterator;

        public SinglyLinkedList()
        {
        }

        public SinglyLinkedList(T data)
        {
            _head = new Node(data);
        }

        public SinglyLinkedList(Node node)
        {
            _head = node;
        }

        public SinglyLinkedList(IEnumerable collection)
        {
            foreach (T item in collection)
            {
                Insert(item);
            }
        }

        #region ICollection> Members

        public void Add(Node item)
        {
            Insert(item);
        }

        public void Clear()
        {
            _head = null;
        }

        public bool Contains(Node item)
        {
            Node found = Find(item);
            return found != null ? false : true;
        }

        public void CopyTo(Node[] array, int arrayIndex)
        {
            throw new NotImplementedException();
        }

        public int Count
        {
            get { return _count; }
        }

        public bool IsReadOnly
        {
            get { return false; }
        }

        public bool Remove(Node item)
        {
            return Delete(item);
        }

        public IEnumerator> GetEnumerator()
        {
            _iterator = _head;
            while (_iterator != null)
            {
                yield return _iterator;
                _iterator = _iterator.Next;
            }
        }

        IEnumerator IEnumerable.GetEnumerator()
        {
            return GetEnumerator();
        }

        #endregion

        public void Insert(T data, InsertionMethod insertionMethod = InsertionMethod.Default)
        {
            _count++;
            Insert(new Node(data), insertionMethod);
        }

        public void Insert(Node node, InsertionMethod insertionMethod = InsertionMethod.Default)
        {
            if (insertionMethod == InsertionMethod.Default || InsertionMethod.Iterative == insertionMethod)
            {
                InsertIteratively(node);
                return;
            }

            InsertRecursively(node);
        }

        private void InsertRecursively(Node node)
        {
            if (_head == null)
            {
                _head = node;
                return;
            }

            Node currentNode = _head;
            InsertRecursively(node, currentNode, null);
        }

        private void InsertRecursively(Node node, Node currentNode, Node previousNode)
        {
            if (currentNode != null)
            {
                InsertRecursively(node, currentNode.Next, currentNode);
                return;
            }

            currentNode = node;
            previousNode.Next = currentNode;
        }

        private void InsertIteratively(Node node)
        {
            if (_head == null)
            {
                _head = node;
                return;
            }

            Node currentNode = _head;

            while (currentNode.Next != null)
            {
                currentNode = currentNode.Next;
            }

            currentNode.Next = node;
        }

        public bool Delete(Node node)
        {
            return true;
        }

        public Node Find(T element)
        {
            foreach (var item in this)
            {
                if (element.Equals(item.Data))
                    return item;
            }
            return null;
        }

        public Node Find(Node node)
        {
            foreach (var element in this)
            {
                if (node.Data.Equals(element.Data))
                    return element;
            }
            return null;
        }

        public void InsertAfter(T data, Node node)
        {
        }

        public void InsertBefore(T data, Node node)
        {
        }

        public bool Replace(T data, Node node)
        {
            return true;
        }

        public bool Contains(T item)
        {
            return Contains(new Node(item));
        }
    }
}

Heap data structure, Binary Heap, is quite useful to keep the min and max access in constant time,O(1). Moreover, Binary heaps can be used to implement priority queues.

Binary heap implementation is quite easy. Below is the code for MinHeap . I need to add the HeapSort which is an efficient comparison based algorithm that takes O(nlogn) for sorting a sequence, Heap sort can be done in place. Basic idea behind Heap sort is to remove the minimum, then take the right most leaf (which is the last element in the array, due to the nature of this structure, which should be a complete tree) and then call heapify method each time after removing the min, removing n nodes takes O(n) time and for each node, we need to call heapify method which cost O(logn), hence overall running time of this algorithm is O(nlogn).

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

namespace FiratAtagun.DataStructures.Heap
{
    public class MinHeap : IEnumerable
    {

        private int[] _collection;
        private int _currentCapacity;
        private const int DefaultCapacity = 20;
        private int _index = 0;

        public MinHeap()
        {
            _collection = new int[DefaultCapacity];
            _currentCapacity = DefaultCapacity;
        }

        public int GetParent(int i, out int index)
        {
            double element = i;
            index = (int)Math.Floor((element - 1)  / 2);

            if(index < 0)
            {
                return 0;
            }

            return _collection[index];
        }

        public int GetLeftChild(int i, out int index)
        {
            index = (2 * i) + 1;
            return _collection[index];
        }

        public int GetRightChild(int i, out int index)
        {
            index = (2 * i) + 2;
            return _collection[index];
        }

        public void Insert(int i)
        {
            _collection[_index] = i;

            HeapifyUp(_index);
            _index++;
        }

        private int _currentIndex;

        private void HeapifyUp(int element)
        {
            int parentIndex;

            int parent = GetParent(element, out parentIndex);

            if (_collection[element] < parent)
            {
                Swap(ref _collection[parentIndex], ref _collection[element]);

            }
            else
            {
                return;
            }

            // Swapped, current element is at parentIndex now, and _index is the parent of the element

            HeapifyUp(parentIndex);

        }

        public void Swap(ref int a, ref int b)
        {
            int temp = a;
            a = b;
            b = temp;
        }

        public int Count
        {
            get { return _index - 1; }
        }

        public int Minimum
        {
            get { return _collection[0]; }
        }

        public int ExtractMinimum()
        {
            int minimum = _collection[0];

            _collection[0] = _collection[--_index];
            _collection[_index] = default(int);

            Heapify();

            return minimum;
        }

        public void Heapify()
        {
            _currentIndex = 0;
            Heapify(_currentIndex);
        }

        public void Heapify(int index)
        {

            int leftChildIndex;
            int rightChildIndex;

            int leftChild = GetLeftChild(index, out leftChildIndex);
            int rightChild = GetRightChild(index, out rightChildIndex);

            if(leftChild == 0 && rightChild == 0)
            {
                return;
            }

            int replacingElement = 0;

            if (leftChild < rightChild)
            {
                replacingElement = leftChildIndex;
            }
            if (leftChild > rightChild)
            {
                replacingElement = rightChildIndex;
            }

            if (leftChild == rightChild)
            {
                replacingElement = leftChildIndex;
            }

            Swap(ref _collection[index], ref _collection[replacingElement]);

            Heapify(replacingElement);
        }

        #region IEnumerable Members

        public IEnumerator GetEnumerator()
        {
            foreach (var i in _collection)
            {
                yield return i;
            }
        }

        #endregion

        #region IEnumerable Members

        System.Collections.IEnumerator System.Collections.IEnumerable.GetEnumerator()
        {
            return GetEnumerator();
        }

        #endregion
    }
}