Find depth of the deepest odd level leaf node in a binary tree

Write a program to find maximum height of the odd level leaf node of a binary tree. The problem has been picked up from GeeksforGeeks

A quick solution will be to use the solution for finding the max depth of the tree and modifying it to calculate the depth using only the odd level leaf nodes.

Read more ...

Find max height of a binary tree

Program for finding maximum depth or height of a binary tree

/**
     * find height of the tree recursively
     */
    public static int maxHeight()
    {
        return maxHeight(root, 0);
    }
 
    private static int maxHeight(Node node, int h)
    {
        if (node == null)
        {
            return h;
        }
 
        int lh = maxHeight(node.left, h + 1);
        int rh = maxHeight(node.right, h + 1);
 
        return (lh > rh) ? lh : rh;
    }

Read more ...

Creating a binary search tree using iterative approach in Java

Program for creating a binary search tree using iterative method

private void addNode(Node node, int n)
{
    while (node != null)
    {
        if(n < node.data)
        {
            if(node.left != null)
            {
                node = node.left;
            }
            else
            {
                node.left = new Node(n);
                return;
            }
        }
        else if(n > node.data)
        {
            if(node.right != null)
            {
                node = node.right;
            }
            else
            {
                node.right = new Node(n);
                return;
            }
        }
        else
        {
            System.out.println("WARNING: Elements are equal");
            return;
        }
    }
}

Read more ...

Creating a binary search tree using recursion in Java

Program for creating binary search tree using recursive method

private void addNode(Node node, int n)
{
    if (n < node.data)
    {
        if (node.left != null)
        {
            addNode(node.left, n);
        }
        else
        {
            node.left = new Node(n);
        }
    }
    else if (n > node.data)
    {
        if (node.right != null)
        {
            addNode(node.right, n);
        }
        else
        {
            node.right = new Node(n);
        }
    }
    else
    {
        System.out.println("WARNING: Number exists already");
    }
}

Read more ...

Insertion Sort in Java using Generics

A generic implementation of Insertion Sort in Java

 1 import org.junit.Assert;
 2 import org.junit.Test;
 3 
 4 class GenericInsertionSorter
 5 {
 6     public <T extends Comparable<T>> void sort(T[] elems) {
 7         int size = elems.length;
 8 
 9         for (int outerLoopIdx = 1; outerLoopIdx < size; ++outerLoopIdx) {
10             for (int innerLoopIdx = outerLoopIdx; innerLoopIdx > 0; --innerLoopIdx) {
11                 if (elems[innerLoopIdx - 1].compareTo(elems[innerLoopIdx]) > 0) {
12                     T temp = elems[innerLoopIdx - 1];
13                     elems[innerLoopIdx - 1] = elems[innerLoopIdx];
14                     elems[innerLoopIdx] = temp;
15                 }
16             }
17         }
18     }
19 }
20 
21 public class InsertionSortTester
22 {
23     private String[] unsortedNames = new String[] {
24             "Pankaj",
25             "Paresh",
26             "Ankit",
27             "Sankalp",
28             "Aditya",
29             "Prem",
30             "Rocket",
31             "Singh",
32             "Alabama",
33             "Alaska",
34             "Animal" };
35 
36     private String[] sortedNames = new String[] {
37             "Aditya",
38             "Alabama",
39             "Alaska",
40             "Animal",
41             "Ankit",
42             "Pankaj",
43             "Paresh",
44             "Prem",
45             "Rocket",
46             "Sankalp",
47             "Singh" };
48 
49     @Test
50     public void testStringSort() {
51         GenericInsertionSorter ss = new GenericInsertionSorter();
52         ss.sort(unsortedNames);
53         Assert.assertArrayEquals(unsortedNames, sortedNames);
54     }
55 }

Read more ...

Insertion Sort in C++ using templates

Insertion Sort
An efficient elementary sort method which places each element in it's proper place among the elements which are already placed

  1 #include <iostream>
  2 #include <string.h>
  3 
  4 template <typename T>
  5 class InsertionSort
  6 {
  7     public:
  8         InsertionSort();
  9         ~InsertionSort();
 10 
 11         void sort(T arr[], int size);
 12     private:
 13         void compareExchange(T arr[], int l, int r);
 14         bool greater(T left, T right);
 15 };
 16 
 17 //Constructor
 18 template <typename T>
 19 InsertionSort<T>::InsertionSort(){}
 20 
 21 //Destructor
 22 template <typename T>
 23 InsertionSort<T>::~InsertionSort(){}
 24 
 25 template <typename T>
 26 void InsertionSort<T>::sort(T arr[], int size)
 27 {
 28     for(int i = 1; i < size; ++i)
 29     {
 30         for(int j = i; j > 0; --j)
 31         {
 32             compareExchange(arr, j-1, j);
 33         }
 34     }
 35 }
 36 
 37 template <typename T>
 38 void InsertionSort<T>::compareExchange(T arr[], int l, int r)
 39 {
 40     if(greater(arr[l], arr[r]))
 41     {
 42         T temp = arr[l];
 43         arr[l] = arr[r];
 44         arr[r] = temp;
 45     }
 46 }
 47 
 48 template <typename T>
 49 bool InsertionSort<T>::greater(T left, T right)
 50 {
 51     return left > right;
 52 }
 53 
 54 template <>
 55 bool InsertionSort<const char*>::greater(const char *left, const char *right)
 56 {
 57     return strcmp(left, right) > 0;
 58 }
 59 
 60 template <typename T>
 61 void print(T arr[], int size)
 62 {
 63     for(int i = 0; i < size; ++i)
 64         std::cout << arr[i] << " ";
 65     std::cout << std::endl;
 66 }
 67 
 68 template <>
 69 void print(std::string arr[], int size)
 70 {
 71     for(int i = 0; i < size; ++i)
 72         std::cout << arr[i].c_str() << " ";
 73     std::cout << std::endl;
 74 }
 75 
 76 template <>
 77 void print(const char *ptrArray, int size)
 78 {
 79     for(int i = 0; i < size; ++i)
 80         std::cout << ptrArray[i] << " ";
 81     std::cout << std::endl;
 82 }
 83 
 84 int main()
 85 {
 86     int arr[] = { 10, 65, 35, 25, 15, 75, 85, 45, 65 };
 87     InsertionSort<int> isInt;
 88     isInt.sort(arr, 9);
 89     print(arr, 9);
 90 
 91     std::string strArr[] = { "pankaj", "paresh", "hello", "world", "ankit", "aditya", "sankalp", "aladdin" };
 92     InsertionSort<std::string> isString;
 93     isString.sort(strArr, 8);
 94     print(strArr, 8);
 95 
 96     const char* ptrArray[] = { "pankaj", "paresh", "hello", "world", "ankit", "aditya", "sankalp", "aladdin", "george"};
 97     InsertionSort<const char*> isPtr;
 98     isPtr.sort(ptrArray, 9);
 99     print(ptrArray, 9);
100 
101     return 0;
102 }

Read more ...

Selection Sort in Java using Generics

A generic implementation of Selection Sort in Java using Generics

 1 import org.junit.Assert;
 2 import org.junit.Test;
 3 
 4 class GenericSelectionSorter
 5 {
 6     public <T extends Comparable<T>> void sort(T[] elems) {
 7         int size = elems.length;
 8 
 9         for (int outerLoopIdx = 0; outerLoopIdx < size - 1; ++outerLoopIdx) {
10             int min = outerLoopIdx;
11             for (int innerLoopIdx = outerLoopIdx; innerLoopIdx < size; ++innerLoopIdx) {
12                 if (elems[min].compareTo(elems[innerLoopIdx]) > 0) {
13                     min = innerLoopIdx;
14                 }
15             }
16 
17             // exchange elements at outerIndexLoop and min positions
18             T temp = elems[min];
19             elems[min] = elems[outerLoopIdx];
20             elems[outerLoopIdx] = temp;
21         }
22     }
23 }
24 
25 public class SelectionSortTester
26 {
27     private String[] unsortedNames = new String[] {
28             "Pankaj",
29             "Paresh",
30             "Ankit",
31             "Sankalp",
32             "Aditya",
33             "Prem",
34             "Rocket",
35             "Singh",
36             "Alabama",
37             "Alaska",
38             "Animal" };
39 
40     private String[] sortedNames = new String[] {
41             "Aditya",
42             "Alabama",
43             "Alaska",
44             "Animal",
45             "Ankit",
46             "Pankaj",
47             "Paresh",
48             "Prem",
49             "Rocket",
50             "Sankalp",
51             "Singh" };
52 
53     @Test
54     public void testStringSort() {
55         GenericSelectionSorter ss = new GenericSelectionSorter();
56         ss.sort(unsortedNames);
57         Assert.assertArrayEquals(unsortedNames, sortedNames);
58     }
59 }

Read more ...

The Selection Sort in C++

Selection Sort
An elementary sorting technique which finds the smallest element in the array and then exchanges it with the element in the first position

 1 #include <iostream>
 2 
 3 class SelectionSort
 4 {
 5     public:
 6         SelectionSort();
 7         ~SelectionSort();
 8 
 9         void sort(int arr[], int size);
10 
11     private:
12         void exchange(int &x, int &y);
13 };
14 
15 //Constructor
16 SelectionSort::SelectionSort() {}
17 
18 //Destructor
19 SelectionSort::~SelectionSort() {}
20 
21 void SelectionSort::sort(int arr[], int size)
22 {
23     for(int outerLoopIdx = 0; outerLoopIdx < size - 1; ++outerLoopIdx)
24     {
25         int min = outerLoopIdx;
26         for(int innerLoopIdx = outerLoopIdx + 1; innerLoopIdx < size; ++innerLoopIdx)
27         {
28             if(arr[min] > arr[innerLoopIdx])
29             {
30                 min = innerLoopIdx;
31             }
32         }
33         exchange(arr[outerLoopIdx], arr[min]);
34     }
35 }
36 
37 void SelectionSort::exchange(int &x, int &y)
38 {
39     int t = x;
40     x = y;
41     y = t;
42 }
43 
44 void print(int arr[], int size)
45 {
46     for(int i = 0; i < size; ++i)
47         std::cout << arr[i] << " ";
48 }
49 
50 int main()
51 {
52     int arr[] = { 10, 65, 35, 25, 15, 75, 85, 45, 65 };
53     SelectionSort ss;
54     ss.sort(arr, 9);
55     print(arr, 9);
56 }

Output:

Read more ...

Bubble Sort in Java using Generics

Below is a generic implementation of Bubble Sort in Java

 1 import org.junit.Assert;
 2 import org.junit.Test;
 3 
 4 class GenericBubbleSorter<T extends Comparable<T>>
 5 {
 6     public void sort(T[] elems) {
 7         int size = elems.length;
 8 
 9         for (int outerLoopIdx = 0; outerLoopIdx < size; ++outerLoopIdx) {
10             for (int innerLoopIdx = 0; innerLoopIdx < (size - outerLoopIdx - 1); ++innerLoopIdx) {
11                 if (elems[innerLoopIdx].compareTo(elems[innerLoopIdx + 1]) > 0) {
12                     T temp = elems[innerLoopIdx];
13                     elems[innerLoopIdx] = elems[innerLoopIdx + 1];
14                     elems[innerLoopIdx + 1] = temp;
15                 }
16             }
17         }
18     }
19 }
20 
21 public class BubbleSortTester
22 {
23     private String[] unsortedNames = new String[] {
24             "Pankaj",
25             "Paresh",
26             "Ankit",
27             "Sankalp",
28             "Aditya",
29             "Prem",
30             "Rocket",
31             "Singh",
32             "Alabama",
33             "Alaska",
34             "Animal" };
35 
36     private String[] sortedNames = new String[] {
37             "Aditya",
38             "Alabama",
39             "Alaska",
40             "Animal",
41             "Ankit",
42             "Pankaj",
43             "Paresh",
44             "Prem",
45             "Rocket",
46             "Sankalp",
47             "Singh" };
48 
49     @Test
50     public void testStringSort() {
51         GenericBubbleSorter<String> bs = new GenericBubbleSorter<String>();
52         bs.sort(unsortedNames);
53         Assert.assertArrayEquals(unsortedNames, sortedNames);
54     }
55 }

Read more ...

The Bubble Sort in C++

Bubble Sort
This sort gets its name from the way smaller/larger elements gets to the top of the list using bubble comparison

 1 #include <iostream>
 2 
 3 class BubbleSort
 4 {
 5     public:
 6         BubbleSort(){}
 7         ~BubbleSort(){}
 8         void sort(int arr[], int size);
 9 };
10 
11 void BubbleSort::sort(int arr[], int size)
12 {
13     //With every iteration in outer loop, the next maximum element is moved to it's correct position
14     for(int outerLoopIdx = 0; outerLoopIdx < size ; ++outerLoopIdx)
15     {
16         for(int innerLoopIdx = 0; innerLoopIdx < (size - outerLoopIdx - 1); ++innerLoopIdx)
17         {
18             //Comparing two subsequent elements OR bubble comparison
19             //Placing the larger element on the right
20             if(arr[innerLoopIdx] > arr[innerLoopIdx + 1])
21             {
22                 int temp = arr[innerLoopIdx];
23                 arr[innerLoopIdx] = arr[innerLoopIdx + 1];
24                 arr[innerLoopIdx + 1] = temp;
25             }
26         }
27     }
28 }
29 
30 void print(int arr[], int size)
31 {
32     for(int i = 0; i < size; ++i)
33         std::cout << arr[i] << " ";
34     std::cout << std::endl;
35 }
36 
37 int main()
38 {
39     int arr[] = { 10, 65, 35, 25, 15, 75, 85, 45, 65 };
40     BubbleSort bs;
41     bs.sort(arr, 9);
42     print(arr, 9);
43     return 0;
44 }

Output

References:
Bubble Sort Animation
Read more ...

Vertical Sum of a Binary Tree

The binary tree above can be represented as the following to calculate the vertical sum of the nodes

Read more ...

Traversing a Binary Tree

There are basically two ways of traversing a binary tree
1. Depth First Traversals
2. Breadth First Traversal

Depth First Traversal
A binary tree can be traversed in three ways using the depth first approach namely

1. Inorder Traversal

template <typename T>
  void BTTraveller<T>::inOrder(BSTNode<T> *node, std::deque<T> &out)
  {
    if(node)
    {
      inOrder(node->left, out);
      out.push_back(node->key);
      inOrder(node->right, out);
    }
  }

2. Preorder Traversal

template <typename T>
  void BTTraveller<T>::preOrder(BSTNode<T> *node, std::deque<T> &out)
  {
    if(node)
    {
      out.push_back(node->key);
      preOrder(node->left, out);
      preOrder(node->right, out);
    }
  }

3. Postorder Traversal

template <typename T>
  void BTTraveller<T>::postOrder(BSTNode<T> *node, std::deque<T> &out)
  {
    if(node)
    {
      postOrder(node->left, out);
      postOrder(node->right, out);
      out.push_back(node->key);
    }
  }

Breadth First Traversal
There is only one kind of Breadth first traversal viz. Level Order traversal. This traversal does not move along the branches of the tree but makes use of a FIFO queue. In the sample code, I have used std::deque as the helper queue for achieving the same.

template <typename T>
  void BTTraveller<T>::levelOrder(BST<T> *bstree, std::deque<T> &out)
  {
    std::deque<BSTNode<T>*> hQ;
    hQ.push_back(bstree->m_root);
    levelOrder(hQ, out);
  }

  template <typename T>
  void BTTraveller<T>::levelOrder(std::deque<BSTNode<T>*> &hQ, std::deque<T> &out)
  {
    while(hQ.empty() == false)
    {
      BSTNode<T> *current = hQ.front();
      if(current != NULL)
      {
        hQ.pop_front();
        out.push_back(current->key);
        addChildren(current, hQ);
      }
    }
  }

The BTTraveller class takes care of returning Binary Tree node elements in the order you are traversing the tree.

 1 #ifndef _BTTraveller_H_
 2 #define _BTTraveller_H_
 3 #include "BSTNode.h"
 4 #include <deque>
 5 
 6 //File: BTTraveller.h
 7 namespace algorithms
 8 {
 9   template <typename T>
10   class BTTraveller
11   {
12   public:
13     static void inOrder(BST<T> *bstree, std::deque<T> &elems);
14     static void preOrder(BST<T> *bstree, std::deque<T> &elems);
15     static void postOrder(BST<T> *bstree, std::deque<T> &elems);
16     static void levelOrder(BST<T> *bstree, std::deque<T> &elems);
17 
18   private:
19     static void inOrder(BSTNode<T> *node, std::deque<T> &elems);
20     static void preOrder(BSTNode<T> *node, std::deque<T> &elems);
21     static void postOrder(BSTNode<T> *node, std::deque<T> &elems);
22     static void levelOrder(std::deque<BSTNode<T>*> &helperQ, std::deque<T> &elems);
23     static void addChildren(BSTNode<T> *node, std::deque<BSTNode<T>*> &helperQ);
24 
25     BTTraveller();
26     BTTraveller(const BTTraveller&);
27     const BTTraveller& operator=(const BTTraveller&);
28   };
29 };
30 
31 #include "BTTraveller.hpp"
32 #endif //_BTTraveller_H_

 1 //File: BTTraveller.hpp
 2 namespace algorithms
 3 {
 4   template <typename T>
 5   void BTTraveller<T>::inOrder(BST<T> *bstree, std::deque<T> &out)
 6   {
 7     inOrder(bstree->m_root, out);
 8   }
 9 
10   template <typename T>
11   void BTTraveller<T>::preOrder(BST<T> *bstree, std::deque<T> &out)
12   {
13     preOrder(bstree->m_root, out);
14   }
15 
16   template <typename T>
17   void BTTraveller<T>::postOrder(BST<T> *bstree, std::deque<T> &out)
18   {
19     postOrder(bstree->m_root, out);
20   }
21 
22   template <typename T>
23   void BTTraveller<T>::levelOrder(BST<T> *bstree, std::deque<T> &out)
24   {
25     std::deque<BSTNode<T>*> hQ;
26     hQ.push_back(bstree->m_root);
27     levelOrder(hQ, out);
28   }
29 
30   template <typename T>
31   void BTTraveller<T>::inOrder(BSTNode<T> *node, std::deque<T> &out)
32   {
33     if(node)
34     {
35       inOrder(node->left, out);
36       out.push_back(node->key);
37       inOrder(node->right, out);
38     }
39   }
40 
41   template <typename T>
42   void BTTraveller<T>::preOrder(BSTNode<T> *node, std::deque<T> &out)
43   {
44     if(node)
45     {
46       out.push_back(node->key);
47       preOrder(node->left, out);
48       preOrder(node->right, out);
49     }
50   }
51 
52   template <typename T>
53   void BTTraveller<T>::postOrder(BSTNode<T> *node, std::deque<T> &out)
54   {
55     if(node)
56     {
57       postOrder(node->left, out);
58       postOrder(node->right, out);
59       out.push_back(node->key);
60     }
61   }
62 
63   template <typename T>
64   void BTTraveller<T>::levelOrder(std::deque<BSTNode<T>*> &hQ, std::deque<T> &out)
65   {
66     while(hQ.empty() == false)
67     {
68       BSTNode<T> *current = hQ.front();
69       if(current != NULL)
70       {
71         hQ.pop_front();
72         out.push_back(current->key);
73         addChildren(current, hQ);
74       }
75     }
76   }
77 
78   template <typename T>
79   void BTTraveller<T>::addChildren(BSTNode<T> *node, std::deque<BSTNode<T>*> &hQ)
80   {
81     if(node->left != NULL)
82     {
83       hQ.push_back(node->left);
84     }
85     if(node->right != NULL)
86     {
87       hQ.push_back(node->right);
88     }
89   }
90 }

You need to include BTTraveller class as a friend class in both the BSTNode as well as BST class declarations. This ensures that the BTTraveller class has access to private data members of these two classes

The BSTNode class

 1 #ifndef _BSTNode_H_
 2 #define _BSTNode_H_
 3 #include <iostream>
 4 
 5 //File: BSTNode.h
 6 namespace algorithms
 7 {
 8   template <typename T>
 9   class BST;
10 
11   template <typename T>
12   class BTTraveller;
13 
14   template <typename T>
15   class BSTNode
16   {
17   public:
18     BSTNode(T key);
19     ~BSTNode();
20 
21     friend class BST<T>;
22     friend class BTTraveller<T>;
23 
24   private:
25     BSTNode<T> *left;
26     BSTNode<T> *right;
27     T key;
28   };
29 };
30 
31 #include "BSTNode.hpp"
32 #endif //_BSTNode_H_

The BST class

 1 #ifndef _BinarySearchTree_H_
 2 #define _BinarySearchTree_H_
 3 #include "BSTNode.h"
 4 
 5 //File: BST.h
 6 namespace algorithms
 7 {
 8   template <typename T>
 9   class BTTraveller;
10 
11   template <typename T>
12   class BST
13   {
14   public:
15     BST();
16     ~BST();
17 
18     //modifiers
19     void insert(T key);
20     void remove(T key);
21     void clear();
22 
23     //accessors
24     bool find(T key);
25     bool isEmpty() const;
26 
27     friend class BTTraveller<T>;
28 
29   private:
30     void remove(BSTNode<T> **node);
31     void clear(BSTNode<T> *node);
32     BSTNode<T>** find(BSTNode<T> **node, const T key);
33     BSTNode<T>** getSuccessor(BSTNode<T> **node);
34     BSTNode<T>* getNewNode(T key);
35 
36     //instance fields
37     BSTNode<T> *m_root;
38   };
39 };
40 
41 #include "BST.hpp"
42 #endif //_BinarySearchTree_H_

The BSTNode.hpp and BST.hpp files remains the same as in the post
The Client Program

 1 #include "BST.h"
 2 #include "BTTraveller.h"
 3 #define MAX 20
 4 using namespace algorithms;
 5 
 6 //File: Main.cpp
 7 
 8 template <typename T>
 9 void DumpDeque(std::deque<T> &q)
10 {
11   std::cout << std::endl;
12   std::deque<T>::const_iterator itr;
13   for(itr = q.cbegin(); itr != q.cend(); ++itr)
14   {
15     std::cout << *itr << " ";
16   }
17   std::cout << std::endl;
18   q.clear();
19 }
20 
21 int main(int argc, char *argv[])
22 {
23   int nodes[MAX] = { 50, 40, 60, 70, 80, 20, 30, 10, 90, 15, 35, 65, 75, 5, 1, 100, 110, 130, 120, 111 };
24   BST<int> bstInt;
25   for(int i = 0; i < MAX; ++i)
26   {
27     bstInt.insert(nodes[i]);
28   }
29 
30   std::deque<int> elems;
31   BTTraveller<int>::inOrder(&bstInt, elems);
32   DumpDeque(elems);
33   BTTraveller<int>::preOrder(&bstInt, elems);
34   DumpDeque(elems);
35   BTTraveller<int>::postOrder(&bstInt, elems);
36   DumpDeque(elems);
37   BTTraveller<int>::levelOrder(&bstInt, elems);
38   DumpDeque(elems);
39 
40   return 0;
41 }

Output

$ ./BinarySearchTree.exe

1 5 10 15 20 30 35 40 50 60 65 70 75 80 90 100 110 111 120 130

50 40 20 10 5 1 15 30 35 60 70 65 80 75 90 100 110 130 120 111

1 5 15 10 35 30 20 40 65 75 111 120 130 110 100 90 80 70 60 50

50 40 60 20 70 10 30 65 80 5 15 35 75 90 1 100 110 130 120 111

Read more ...

A Binary Search Tree Example

A Binary Tree is a tree where each node may have 0, 1 or 2 children and a Binary Search Tree is a binary tree with a special property that the value of node under discussion is less than all the nodes in its right subtree and greater than all the nodes in its left subtree.
The programs below describes the three basic operations in a binary search tree viz. search, insert and remove

1. Searching a node

  template <typename T>
  BSTNode<T>** BST<T>::find(BSTNode<T> **node, const T key)
  {
    if(*node == NULL || (*node)->key == key)
    {
      return node;
    }
    else if((*node)->key > key)
    {
      return find(&(*node)->left, key);
    }
    else
    {
      return find(&(*node)->right, key);
    }
  }

2. Inserting a node

template <typename T>
  void BST<T>::insert(T key)
  {
    BSTNode<T> **node = find(&m_root, key);
    if(*node == NULL)
    {
      *node = getNewNode(key);
    }
  }

3. Removing a node
Removing a node from binary search tree is the trickiest of all the operations. There are three cases to be considered when removing a node from a binary search tree:

Case 1. If both left and right child are null, the node can simply be deleted.

Case 2. If only one of the right child or left child is null, the address of the node is set to point to the left child or the right child which ever is not null and the current node is deleted.

Case 3. The complex of the three cases, if both left and right child are present. This requires finding the successor of the current node which is to be removed.

template <typename T>
  void BST<T>::remove(BSTNode<T> **node)
  {
    BSTNode<T> *old = *node;
    if((*node)->left == NULL)
    {
      *node = (*node)->right;
      delete old;
    }
    else if((*node)->right == NULL)
    {
      *node = (*node)->left;
      delete old;
    }
    else
    {
      BSTNode<T> **successor = getSuccessor(node);
      (*node)->key = (*successor)->key;
      remove(successor);
    }
  }

Following is the complete example showing the implementation details of the search, find and remove operations in a binary search tree.

The BST Node Class

 1 #ifndef _BSTNode_H_
 2 #define _BSTNode_H_
 3 #include <iostream>
 4 
 5 //File: BSTNode.h
 6 namespace algorithms
 7 {
 8   template <typename T>
 9   class BST;
10 
11   template <typename T>
12   class BSTNode
13   {
14   public:
15     BSTNode(T key);
16     ~BSTNode();
17 
18     friend class BST<T>;
19 
20   private:
21     BSTNode<T> *left;
22     BSTNode<T> *right;
23     T key;
24   };
25 };
26 
27 #include "BSTNode.hpp"
28 #endif //_BSTNode_H_

 1 //File: BSTNode.hpp
 2 namespace algorithms
 3 {
 4   template <typename T>
 5   BSTNode<T>::BSTNode(T key) : left(0), right(0)
 6   {
 7     this->key = key;
 8   }
 9 
10   template <typename T>
11   BSTNode<T>::~BSTNode()
12   {
13   }
14 }
15 

The Binary Search Tree Class

 1 #ifndef _BinarySearchTree_H_
 2 #define _BinarySearchTree_H_
 3 #include "BSTNode.h"
 4 
 5 //File: BST.h
 6 namespace algorithms
 7 {
 8   template <typename T>
 9   class BST
10   {
11   public:
12     BST();
13     ~BST();
14 
15     //modifiers
16     void insert(T key);
17     void remove(T key);
18     void clear();
19 
20     //accessors
21     bool find(T key);
22     bool isEmpty() const;
23 
24   private:
25     void remove(BSTNode<T> **node);
26     void clear(BSTNode<T> *node);
27     BSTNode<T>** find(BSTNode<T> **node, const T key);
28     BSTNode<T>** getSuccessor(BSTNode<T> **node);
29     BSTNode<T>* getNewNode(T key);
30 
31     //instance fields
32     BSTNode<T> *m_root;
33   };
34 };
35 
36 #include "BST.hpp"
37 #endif //_BinarySearchTree_H_

  1 //File: BST.hpp
  2 namespace algorithms
  3 {
  4   template <typename T>
  5   BST<T>::BST()
  6   {
  7     m_root = 0;
  8   }
  9 
 10   template <typename T>
 11   BST<T>::~BST()
 12   {
 13     clear();
 14   }
 15 
 16   template <typename T>
 17   void BST<T>::clear()
 18   {
 19     clear(m_root);
 20   }
 21 
 22   template <typename T>
 23   void BST<T>::clear(BSTNode<T> *node)
 24   {
 25     if(node != NULL)
 26     {
 27       clear(node->left);
 28       clear(node->right);
 29       delete node;
 30     }
 31   }
 32 
 33   template <typename T>
 34   void BST<T>::insert(T key)
 35   {
 36     BSTNode<T> **node = find(&m_root, key);
 37     if(*node == NULL)
 38     {
 39       *node = getNewNode(key);
 40     }
 41   }
 42 
 43   template <typename T>
 44   void BST<T>::remove(T key)
 45   {
 46     BSTNode<T> **node = find(&m_root, key);
 47     remove(node);
 48   }
 49 
 50   template <typename T>
 51   void BST<T>::remove(BSTNode<T> **node)
 52   {
 53     BSTNode<T> *old = *node;
 54     if((*node)->left == NULL)
 55     {
 56       *node = (*node)->right;
 57       delete old;
 58     }
 59     else if((*node)->right == NULL)
 60     {
 61       *node = (*node)->left;
 62       delete old;
 63     }
 64     else
 65     {
 66       BSTNode<T> **successor = getSuccessor(node);
 67       (*node)->key = (*successor)->key;
 68       remove(successor);
 69     }
 70   }
 71 
 72   template <typename T>
 73   BSTNode<T>** BST<T>::getSuccessor(BSTNode<T> **node)
 74   {
 75     BSTNode<T> **tmp = &(*node)->left;
 76     while((*tmp)->right != NULL)
 77     {
 78       tmp = &(*tmp)->right;
 79     }
 80     return tmp;
 81   }
 82 
 83   template <typename T>
 84   bool BST<T>::find(const T key)
 85   {
 86     BSTNode<T> **pos = find(&m_root, key);
 87     return *pos != NULL;
 88   }
 89 
 90   template <typename T>
 91   bool BST<T>::isEmpty() const
 92   {
 93     return m_root == 0;
 94   }
 95 
 96   template <typename T>
 97   BSTNode<T>** BST<T>::find(BSTNode<T> **node, const T key)
 98   {
 99     if(*node == NULL || (*node)->key == key)
100     {
101       return node;
102     }
103     else if((*node)->key > key)
104     {
105       return find(&(*node)->left, key);
106     }
107     else
108     {
109       return find(&(*node)->right, key);
110     }
111   }
112 
113   template <typename T>
114   BSTNode<T>* BST<T>::getNewNode(T key)
115   {
116     BSTNode<T> *node = new BSTNode<T>(key);
117     if(node == NULL)
118     {
119       std::cerr << "ERROR: Insufficient Memory";
120       std::cerr << std::endl;
121     }
122     return node;
123   }
124 }

The Client Program for testing the BST code above

 1 #include "BST.h"
 2 #define MAX 20
 3 using namespace algorithms;
 4 
 5 //File: Main.cpp
 6 int main(int argc, char *argv[])
 7 {
 8   int nodes[MAX] = { 50, 40, 60, 70, 80, 20, 30, 10, 90, 15, 35, 65, 75, 5, 1, 100, 110, 130, 120 };
 9   BST<int> bstInt;
10   for(int i = 0; i < MAX; ++i)
11   {
12     bstInt.insert(nodes[i]);
13   }
14 
15   std::cout << (bstInt.find(130) ? "true" : "false");
16   bstInt.remove(50);
17   std::cout << (bstInt.find(50)  ? "true" : "false");
18 
19   return 0;
20 }

Output of the run
$ ./BinarySearchTree.exe
truefalse

Read more ...

Knuth Morris Pratt Algorithm

The KMP algorithm compares the pattern string to the text in left to right direction as compared to Boyer Moore Algorithm. The algorithm shifts the pattern more intelligently than the brute-force algorithm.

Key Idea
Whenever a mismatch occurs, what is the most we can shift the pattern so as to avoid redundant comparisons?
Answer: The largest prefix of P[0..j] that is a suffix of [1..j]

The KMP algorithm pre-processes the pattern string to find matches of the prefixes of the pattern with the pattern itself. The information thus calculated is used to shift the pattern appropriately whenever a mismatch occurs or a comparison fails. The compuatation is performed by the function called KMP prefix function

KMP Prefix Function
The prefix function F(j) is defined as the size of the largest prefix in P[0..j] that is also a suffix of P[1..j]

Code for computing the KMP Prefix Function

computeKmpPrefix(const std::string &pattern){
    int patternSize = pattern.size();
    vector<int> kmpPrefix(patternSize);
    size_t prefixPos = 0;
    size_t suffixPos = 1;

    while(suffixPos < patternSize){
        if(pattern[prefixPos] == pattern[suffixPos]){
            kmpPrefix[suffixPos] = prefixPos + 1;
            prefixPos++;
            suffixPos++;
        }
        else if(prefixPos > 0){//found some match
            prefixPos = kmpPrefix[prefixPos -1];//backtrack for matching prefix   e.g. aaaaabaaaaaa
        }
        else{
            kmpPrefix[suffixPos] = 0;
            suffixPos++;
        }
    }
    return kmpPrefix;
}

The algorithm in picture

Example

The Complete Code

#ifndef _PatternMatcher_H_
#define _PatternMatcher_H_

#include <iostream>

#include <string>
#include <vector>

using namespace std;

class PatternMatcher{
public:
    static int kmpSearch(const string& text, const string& pattern);

private:
    static vector<int> computeKmpPrefix(const string& pattern);

    PatternMatcher();
    PatternMatcher(const PatternMatcher&);
    const PatternMatcher& operator=(const PatternMatcher&);
};

#endif //_PatternMatcher_H_

#include "PatternMatcher.h"

vector<int> PatternMatcher::computeKmpPrefix(const std::string &pattern){
    int patternSize = pattern.size();
    vector<int> kmpPrefix(patternSize);
    size_t prefixPos = 0;
    size_t suffixPos = 1;

    while(suffixPos < patternSize){
        if(pattern[prefixPos] == pattern[suffixPos]){
            kmpPrefix[suffixPos] = prefixPos + 1;
            prefixPos++;
            suffixPos++;
        }
        else if(prefixPos > 0){//found some match
            prefixPos = kmpPrefix[prefixPos -1];//backtrack for matching prefix e.g. aaaaabaaaaaa
        }
        else{
            kmpPrefix[suffixPos] = 0;
            suffixPos++;
        }
    }
    return kmpPrefix;
}

int PatternMatcher::kmpSearch(const std::string &text, const std::string &pattern){

    size_t textSize = text.size();
    size_t patternSize = pattern.size();

    if(patternSize > textSize)
        return -1;

    vector<int> kmpNext = computeKmpPrefix(pattern);
    int tIdx = 0;
    int pIdx = 0;

    while(tIdx < textSize){
        if(pattern[pIdx] == text[tIdx]){
            if(pIdx == patternSize - 1) 
                return tIdx - (patternSize - 1);
            tIdx++;
            pIdx++;
        }
        else if(pIdx > 0){
            pIdx = kmpNext[pIdx - 1];
        }
        else{
            tIdx++;
        }
    }
    return -1;
}

#include "PatternMatcher.h"

int main(){
    cout << PatternMatcher::kmpSearch
        ("abacaabaccabacabaabb", "abacab")
        << endl;
    cout << PatternMatcher::kmpSearch
        ("abacaabaccabacabaabb", "baabb")
        << endl;
    cout << PatternMatcher::kmpSearch
        ("abacaabaccabacabaabb", "abacad")
        << endl;
    cout << PatternMatcher::kmpSearch
        ("abacaabaccabacabaabb", "abacaab")
        << endl;
    cout << PatternMatcher::kmpSearch
        ("abacaabaccabacabaabb", "abacab")
        << endl;
    cout << PatternMatcher::kmpSearch
        ("abacaabaccabacabaabb", "aabaccaba")
        << endl;
    cout << PatternMatcher::kmpSearch
        ("abacaabaccabacabaabb", "abacaabaccabacabaabb")
        << endl;
    cout << PatternMatcher::kmpSearch
        ("abacaabaccabacabaabb", "")
        << endl;
    cout << PatternMatcher::kmpSearch
        ("", "abacaabaccabacabaabb")
        << endl;
    cout << PatternMatcher::kmpSearch
        ("abacaabaccabacabaabb", "bacaabaccabacabaab")
        << endl;
    cout << PatternMatcher::kmpSearch
        ("abacaabaccabacabaabb", "abacaabac")
        << endl;
    cout << PatternMatcher::kmpSearch
        ("abacaabaccabacabaabb", "ccabacabaabb")
        << endl;
    cout << PatternMatcher::kmpSearch
        ("abacaabaccabacabaabb", "bacaabaccabacabaabb")
        << endl;
    return 0;
}

Read more ...

Boyer Moore Algorithm

Boyer Moore Algorithm is one of the fastest pattern searching algorithm based on two techniques:

Techniques Used
1. The looking glass technique where you find a pattern P in text T by moving backwards through P, starting at it's end.
2. The character jump heuristic when a mismatch occurs between the characters at position Text[t] = c

Three cases are checked in the order for calculating the character jump. Before moving on to understand the individual cases, let us understand the computation of last occurrence position in the pattern string

Computing last occurrence
The compute last occurrence method assumes that all the characters under the consideration are ASCII characters. The function computes last occurrences of all the characters present in the Pattern P starting from the left. The rest of the ASCII chars return -1

Consider the ASCII character set {a, b, c, d, ..., y, z} then the last occurrence function would be computed as shown in the figure below

The function f(x) points to the last occurrence of character in the pattern P

computeBmpLast(const std::string &pattern){
    const size_t NUM_ASCII_CHARS = 128;
    vector<int> bmpLast(NUM_ASCII_CHARS);

    for(size_t i = 0; i < NUM_ASCII_CHARS; i++){
        bmpLast[i] = -1;
    }

    for(size_t i = 0; i < pattern.size(); i++){
        bmpLast[pattern[i]] = i;
    }
    return bmpLast;
}

Character Jump Heuristics

Case 1:
The character mismatch occurs at the location T[t] = 'x' and the character 'x' is found to the left of the character P[p] = 'c' OR 1 + f(T[t]) <= p. In this case move pattern P to the right to align last occurrence of x in P with x in T

tnew = t + length of pattern - ( 1 + last occurrence of 'x' in pattern)
pnew = length of pattern - 1

Case 2:
The character mismatch occurs at the location T[t] = 'x' and the character 'x' is found to the right of the character P[p] = 'c' OR 1 + f(T[t]) > p. In this scenario alignment is not possible by moving the pattern to the right on the basis of last occurrence. Here we shift the pattern by 1 so that P[p] = c aligns with T[t+1] = a

tnew = t + length of pattern - p
pnew = length of pattern - 1

Case 3:
If the case 1 and case 2 cannot be applied, that means the character T[t] is not found in the pattern P. In this case, we move the pattern P so that P[0] = x aligns itself with T[t+1] = a

tnew = t + length of pattern
pnew = length of pattern - 1

//Character Jump Heuristics
int lastOccur = bmpLast[text[tIdx]];
if(lastOccur != -1){
    if(pIdx > lastOccur){// Case 1: last occurrence of char is to left or equal to the mismatch point 
        tIdx = tIdx + patternSize - (1 + lastOccur);
        pIdx = patternSize - 1;
    }
    else{// Case 2: last occurrence of char is to right of the mismatch point
        tIdx = tIdx + patternSize - (pIdx);
        pIdx = patternSize - 1;
    }
}
else{// Case 3: character is not found in the pattern string
    tIdx = tIdx + patternSize;
    pIdx = patternSize - 1;
}

Merging Case 1 and Case 2 in the above code

//Character Jump Heuristics
int lastOccur = bmpLast[text[tIdx]];
if(lastOccur != -1){
    tIdx = tIdx + patternSize - min<int>(pIdx, 1 + lastOccur);
}
else{// Case 3: character is not found in the pattern string
    tIdx = tIdx + patternSize;
}
pIdx = patternSize - 1;

In our case as computeBmpLast() function stores -1 for characters not found in the search pattern. We can safely merge the Case 3 in the above code to look as

//Character Jump Heuristics
int lastOccur = bmpLast[text[tIdx]];
tIdx = tIdx + patternSize - min<int>(pIdx, 1 + lastOccur);
pIdx = patternSize - 1;

Example:



Complete Code Example

#ifndef _PatternMatcher_H_
#define _PatternMatcher_H_
#include <iostream>
#include <string>
#include <vector>
using namespace std;
class PatternMatcher{
public:
    static int bmpSearch(const string& text, const string& pattern);

private:
    static vector<int> computeBmpLast(const string& pattern);

    PatternMatcher();
    PatternMatcher(const PatternMatcher&);
    const PatternMatcher& operator=(const PatternMatcher&);
};
#endif //_PatternMatcher_H_

#include "PatternMatcher.h"
#include <algorithm>

using namespace std;

int PatternMatcher::bmpSearch(const std::string &text, const std::string &pattern){
    size_t textSize = text.size();
    size_t patternSize = pattern.size();
    if(textSize == 0 || patternSize == 0){
        return -1;
    }
    if(patternSize > textSize){
        return -1;
    }

    vector<int> bmpLast = computeBmpLast(pattern);
    size_t tIdx = patternSize - 1;
    size_t pIdx = patternSize - 1;
    while(tIdx < textSize){
        if(pattern[pIdx] == text[tIdx]){
            if(pIdx == 0){   //found a match
                return tIdx;
            }
            tIdx--;
            pIdx--;
        }
        else {
            //Character Jump Heuristics
            int lastOccur = bmpLast[text[tIdx]];
            tIdx = tIdx + patternSize - min<int>(pIdx, 1 + lastOccur);
            pIdx = patternSize - 1;
        }
    }
    return - 1;
}

vector<int> PatternMatcher::computeBmpLast(const std::string &pattern){
    const size_t NUM_ASCII_CHARS = 128;
    vector<int> bmpLast(NUM_ASCII_CHARS);
    for(size_t i = 0; i < NUM_ASCII_CHARS; i++){
        bmpLast[i] = -1;
    }
    for(size_t i = 0; i < pattern.size(); i++){
        bmpLast[pattern[i]] = i;
    }
    return bmpLast;
}

#include "PatternMatcher.h"

int main(){
    cout << PatternMatcher::bmpSearch
        ("abacaabaccabacabaabb", "abacab")
        << endl;
    cout << PatternMatcher::bmpSearch
        ("abacaabaccabacabaabb", "baabb")
        << endl;
    cout << PatternMatcher::bmpSearch
        ("abacaabaccabacabaabb", "abacad")
        << endl;
    cout << PatternMatcher::bmpSearch
        ("abacaabaccabacabaabb", "abacaab")
        << endl;
    cout << PatternMatcher::bmpSearch
        ("abacaabaccabacabaabb", "abacab")
        << endl;
    cout << PatternMatcher::bmpSearch
        ("abacaabaccabacabaabb", "aabaccaba")
        << endl;
    cout << PatternMatcher::bmpSearch
        ("abacaabaccabacabaabb", "abacaabaccabacabaabb")
        << endl;
    cout << PatternMatcher::bmpSearch
        ("abacaabaccabacabaabb", "")
        << endl;
    cout << PatternMatcher::bmpSearch
        ("", "abacaabaccabacabaabb")
        << endl;
    cout << PatternMatcher::bmpSearch
        ("abacaabaccabacabaabb", "bacaabaccabacabaab")
        << endl;
    cout << PatternMatcher::bmpSearch
        ("abacaabaccabacabaabb", "abacaabac")
        << endl;
    cout << PatternMatcher::bmpSearch
        ("abacaabaccabacabaabb", "ccabacabaabb")
        << endl;
    cout << PatternMatcher::bmpSearch
        ("abacaabaccabacabaabb", "bacaabaccabacabaabb")
        << endl;

    return 0;
}

Read more ...