Power of Eloquence

When saying “Hello World!” isn’t enough anymore

Know Your Algorithms and Data Structures - in Any Language - Part 3

| Comments

First of all - Happy New Year of 2019 to all! 👑🎉🎊

To kick off the year with a big bang, let’s start with today’s post.

From my previous post little over ago or so, I discussed the importance of knowing data structures such as arrays, stacks, queues etc every good software developer/engineer must grasp. In this post, I will be covering topics on the other not-so-common data structures that we normally (or always, should I say) use when implementing our algorithms. They are follows:

  1. Trees
  2. Graphs
  3. Heaps
  4. Trie

Data Structures

a) Trees

Binary Tree

A binary tree is a tree whose elements have at most 2 children. Each element in a binary tree can have only 2 children thus we typically name them left and right nodes respectively. Typically a tree node has the following properties

  1. Data
  2. Left Pointer
  3. Right Pointer

The top most node in the tree is called the root. Every node (except the root node) in a tree is connected by a directed edge from exactly one node to another. This node is called the parent node. Sometimes, a node can have more than 2 connected nodes to itself. Nodes with no children are called leaves or external nodes. Nodes which are not leaves are called internal nodes.

Next, we have a special kind of binary tree called the Binary Search Tree (BST). This tree is mainly used for storing repository that offers efficient ways of sorting, searching and retrieving data. A BST is a binary tree where nodes are ordered in the following way:

  • each node contains a key (or data)
  • the keys in the left subtree are less than the key in its parent node.
  • the keys in the right subtree are greater than the key in its parent node.
  • duplicate keys are not allowed.

Finally, we have a binary tree traversal which is a process that visits all the nodes in the trees. When traversing trees, we consider a couple of traversal search approaches for doing such exercise.

  • Depth First Search
  • Breath First Search

Using depth first search approach, we have the following types of traversals to pick on:

  • Preorder traversal - visit parent first, then left and right children.
  • Inorder traversal - visit the left first, then parent and right child.
  • Postorder traversal - visit the left first, then right child and parent.

With breadth-first search, there’s one type of traversal method which is level order traversal. This type of traversal visits nodes by levels from top to bottom and from left to right. Binary Trees and Binary Search Trees . Binary Tree Traversal.

All popular programming languages I know or aware of supports them - such as the following.

Java

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
import java.util.*;
public class BinaryTree {
    Node root;
    public void add(int value) {
        root = addRecursive(root, value);
    }
    private Node addRecursive(Node current, int value) {
        if (current == null) {
            return new Node(value);
        }
        if (value < current.value) {
            current.left = addRecursive(current.left, value);
        } else if (value > current.value) {
            current.right = addRecursive(current.right, value);
        }
        return current;
    }
    public boolean isEmpty() {
        return root == null;
    }
    public int getSize() {
        return getSizeRecursive(root);
    }
    private int getSizeRecursive(Node current) {
        return current == null ? 0 : getSizeRecursive(current.left) + 1 + getSizeRecursive(current.right);
    }
    public boolean containsNode(int value) {
        return containsNodeRecursive(root, value);
    }
    private boolean containsNodeRecursive(Node current, int value) {
        if (current == null) {
            return false;
        }
        if (value == current.value) {
            return true;
        }
        return value < current.value
          ? containsNodeRecursive(current.left, value)
          : containsNodeRecursive(current.right, value);
    }
    public void delete(int value) {
        root = deleteRecursive(root, value);
    }
    private Node deleteRecursive(Node current, int value) {
        if (current == null) {
            return null;
        }
        if (value == current.value) {
            // Case 1: no children
            if (current.left == null && current.right == null) {
                return null;
            }
            // Case 2: only 1 child
            if (current.right == null) {
                return current.left;
            }
            if (current.left == null) {
                return current.right;
            }
            // Case 3: 2 children
            int smallestValue = findSmallestValue(current.right);
            current.value = smallestValue;
            current.right = deleteRecursive(current.right, smallestValue);
            return current;
        }
        if (value < current.value) {
            current.left = deleteRecursive(current.left, value);
            return current;
        }
        current.right = deleteRecursive(current.right, value);
        return current;
    }
    private int findSmallestValue(Node root) {
        return root.left == null ? root.value : findSmallestValue(root.left);
    }
    public void traverseInOrder(Node node) {
        if (node != null) {
            traverseInOrder(node.left);
            System.out.print(" " + node.value);
            traverseInOrder(node.right);
        }
    }
    public void traversePreOrder(Node node) {
        if (node != null) {
            System.out.print(" " + node.value);
            traversePreOrder(node.left);
            traversePreOrder(node.right);
        }
    }
    public void traversePostOrder(Node node) {
        if (node != null) {
            traversePostOrder(node.left);
            traversePostOrder(node.right);
            System.out.print(" " + node.value);
        }
    }
    public void traverseLevelOrder() {
        if (root == null) {
            return;
        }
        Queue<Node> nodes = new LinkedList<>();
        nodes.add(root);
        while (!nodes.isEmpty()) {
            Node node = nodes.remove();
            System.out.print(" " + node.value);
            if (node.left != null) {
                nodes.add(node.left);
            }
            if (node.left != null) {
                nodes.add(node.right);
            }
        }
    }
    class Node {
        int value;
        Node left;
        Node right;
        Node(int value) {
            this.value = value;
            right = null;
            left = null;
        }
    }
}

Python

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
#!/usr/bin/python
class Node:
      def __init__(self,info):
          self.info = info
          self.left = None
          self.right = None
          self.level = None
      def __str__(self):
          return str(self.info)
class BinarySearchTree:
      def __init__(self): #constructor of class
          self.root = None
      def create(self,val):  #create binary search tree nodes
          if self.root == None:
             self.root = Node(val)
          else:
             current = self.root
             while 1:
                 if val < current.info:
                   if current.left:
                      current = current.left
                   else:
                      current.left = Node(val)
                      break;
                 elif val > current.info:
                    if current.right:
                       current = current.right
                    else:
                       current.right = Node(val)
                       break;
                 else:
                    break
      def inorder(self,node):
           if node is not None:
              self.inorder(node.left)
              print node.info
              self.inorder(node.right)
      def preorder(self,node):
           if node is not None:
              print node.info
              self.preorder(node.left)
              self.preorder(node.right)
      def postorder(self,node):
           if node is not None:
              self.postorder(node.left)
              self.postorder(node.right)
              print node.info

Ruby

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
#!/usr/bin/ruby
class BinarySearchTree
  class Node
    attr_reader :key, :left, :right

    def initialize( key )
      @key = key
      @left = nil
      @right = nil
    end

    def insert( new_key )
      if new_key <= @key
        @left.nil? ? @left = Node.new( new_key ) : @left.insert( new_key )
      elsif new_key > @key
        @right.nil? ? @right = Node.new( new_key ) : @right.insert( new_key )
      end
    end
  end

  def initialize
    @root = nil
  end

  def insert( key )
    if @root.nil?
      @root = Node.new( key )
    else
      @root.insert( key )
    end
  end

  def in_order(node=@root, &block)
    return if node.nil?
    in_order(node.left, &block)
    yield node
    in_order(node.right, &block)
  end

  def pre_order(node=@root, &block)
    return if node.nil?
    yield node
    pre_order(node.left, &block)
    pre_order(node.right, &block)
  end

  def post_order(node=@root, &block)
    return if node.nil?
    post_order(node.left, &block)
    post_order(node.right, &block)
    yield node
  end

  def search( key, node=@root )
    return nil if node.nil?
    if key < node.key
      search( key, node.left )
    elsif key > node.key
      search( key, node.right )
    else
      return node
    end
  end
  def check_height(node)
    return 0 if node.nil?
    leftHeight = check_height(node.left)
    return -1 if leftHeight == -1
    rightHeight = check_height(node.right)
    return -1 if rightHeight == -1
    diff = leftHeight - rightHeight
    if diff.abs > 1
      -1
    else
      [leftHeight, rightHeight].max + 1
    end
  end
  def is_balanced?(node=@root)
    check_height(node) == -1 ? false : true
  end
end

Javascript

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
class Node {

  constructor(data, left, right) {
    this.data = data;
    this.left = left;
    this.right = right;
  }
  insert(new_data) {
    if new_data <= this.data {
        if (this.left == null ?)  {
          this.left = new Node( new_data )
        }
        else {
          this.left.insert( new_data )
        }
    }
    else if (new_data > this.data) {
        if(this.right == null) {
          this.right = new Node( new_data )
        }
        else{
          this.right.insert( new_data )
        }
    }
  }
}

class BinarySearchTree {
  constructor() {
    this.root = null;
  }
  insertNode(new_data) {
    if (this.root == null) {
      this.root = new Node(new_data)
    }
    else {
      this.root.insert(new_data)
    }
  }
  inOrderTraversal(node) {
    if(node == null) {
      return
    }
    in_order(node.left)
    console.log(node)
    in_order(node.right)
  }


  preOrderTraversal(node) {
    if(node == null) {
      return
    }
    console.log(node)
    inOrderTraversal(node.left)
    inOrderTraversal(node.right)
  }

  postOrderTraversal(node) {
    if(node == null) {
      return
    }
    inOrderTraversal(node.left, &block)
    inOrderTraversal(node.right, &block)
    console.log(node)
  }

  search(data, node ) {
    if(node == null) {
      return null;
    }
    if (data < node.data) {
      search(data, node.left)
    } else if(data > node.data) {
      search(key, node.right)
    } else {
      return node;
    }
  }
  checkHeight(node) {
    if(node == null) {
      return 0;
    }
    leftHeight = checkHeight(node.left)
    if (leftHeight === -1) {
      return -1;
    }
    rightHeight = checkHeight(node.right)
    if (rightHeight === -1) {
      return -1;
    }
    diff = leftHeight - rightHeight
    if  Math.abs(diff) > 1
      return -1
    else
      return Math.max(leftHeight, rightHeight) + 1
    end
  }
  isBalanced(node){
    return (checkHeight(node) === -1) ? false : true
  }
}

C++

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
#include <iostream>
#include <stdio.h>
#include <stdlib.h>
struct node {
    int data;
    struct node *left, *right;
};
struct node *newNode(int data) {
    struct node *temp = (struct node *)malloc(sizeof(struct node));
    temp->data = data;
    temp->left = temp->right = NULL;
    return temp;
}
void inorder(struct node *root) {
    if(root != NULL) {
        inorder(root->left);
        printf(%d \n, root->key);
        inorder(root->right);
    }
}

void preorder(struct node *root) {
    if(root != NULL) {
        printf(%d \n, root->key);
        preorder(root->left);
        preorder(root->right);
    }
}
void postorder(struct node *root) {
    if(root != NULL) {
        postorder(root->left);
        postorder(root->right);
        printf(%d \n, root->key);
    }
}
struct node* insert(struct node* new_node, int new_data) {
    if(new_node == NULL) return newNode(new_data);
    if(new_data < new_node->key)
        new_node-> left = insert(new_node->left, new_data);
    else if(new_data > new_node->key)
        new_node->right = insert(new_node->right, new_data)
    return new_node;
}
int getHeight(struct node *current_node) {
    if(current_node) return 0;
    return 1 + max(getHeight(current_node->left), getHeight(current_node->right));
}
bool isBalanced(struct node *current_node) {
    if(!current_node){
        return false;
    }
    int leftHeight = getHeight(current_node->left);
    int rightHeight = getHeight(current_node->right);
    if (abs(leftHeight - rightHeight) > 1)
      return
}

PHP

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
<?php
    class Node {
          public $info;
          public $left;
          public $right;
          public $level;
          public function __construct($info) {
                 $this->info = $info;
                 $this->left = NULL;
                 $this->right = NULL;
                 $this->level = NULL;
          }
          public function __toString() {
                 return "$this->info";
          }
    }
    class SearchBinaryTree {
      public $root;
      public function  __construct() {
             $this->root = NULL;
      }
      public function create($info) {

             if($this->root == NULL) {
                $this->root = new Node($info);
             } else {
                $current = $this->root;
                while(true) {
                      if($info < $current->info) {

                            if($current->left) {
                               $current = $current->left;
                            } else {
                               $current->left = new Node($info);
                               break;
                            }
                      } else if($info > $current->info){
                            if($current->right) {
                               $current = $current->right;
                            } else {
                               $current->right = new Node($info);
                               break;
                            }
                      } else {
                        break;
                      }
                }
             }
      }
      public function traverse($method) {
             switch($method) {
                 case 'inorder':
                 $this->_inorder($this->root);
                 break;
                 case 'postorder':
                 $this->_postorder($this->root);
                 break;
                 case 'preorder':
                 $this->_preorder($this->root);
                 break;
                 default:
                 break;
             }
      }
      private function _inorder($node) {
                      if($node->left) {
                         $this->_inorder($node->left);
                      }
                      echo $node. " ";
                      if($node->right) {
                         $this->_inorder($node->right);
                      }
      }
      private function _preorder($node) {
                      echo $node. " ";
                      if($node->left) {
                         $this->_preorder($node->left);
                      }
                      if($node->right) {
                         $this->_preorder($node->right);
                      }
      }
      private function _postorder($node) {
                      if($node->left) {
                         $this->_postorder($node->left);
                      }
                      if($node->right) {
                         $this->_postorder($node->right);
                      }
                      echo $node. " ";
      }
}

b) Graphs

Graph

Next, we have a graphs.

Like trees, a graph is a non-linear data structure that consist of nodes and edges. The nodes are sometimes called vertices and edges are called lines or arcs for there may be more than two nodes connected to each other in the graph.

Graphs are used to solve many real-life problems. Graphs are used to represent networks. The networks may include paths in a city or telephone network or circuit network. Graphs are also used in social networks like LinkeIn, Facebook,

Java

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
import java.util.*;
public class Vertex{
    private int label;
    Vertex(String label) {
        this.label = label;
    }
    //equals and hashCode

    @Override
    public boolean equals(Object obj) {
        if(this == obj) return true;
        if(! (obj instanceof Vertext)) return false;
        Vertex _obj = (Vertex) obj;
        return _obj.label = this.label;
    }

    @Override
    public int hashCode() {
        return label;
    }
    @Override
    public int getLabel(){
        return label;
    }
    @Override
    public void setLabel(int newValue){
        this.label = newValue;
    }
}
public class Graph {
    private Map<Vertex, List<Vertex>> adjVertices;

    public Graph() {
       adjVertices = new Map<>()
   }
    public void addVertex(int label) {
       adjVertices.add(new Vertex(label), new ArrayList<>());
   }
    public void removeVertex(int label) {
      Vertex v = new Vertex(label);
        adjVertices.values()
            .stream()
            .map(e -> e.remove(v))
            .collect(Collectors.toList());
        adjVertices.remove(new Vertex(label));
    }
   public void addEdge(int label1, int label2 ){
       Vertex v1 = new Vertex(label1);
       Vertex v2 = new Vertex(label2);
        adjVertices.get(v1).add(v2);
        adjVertices.get(v2).add(v1);
    }
    public void removeEdge(int label1, int label2) {
        Vertex v1 = new Vertex(label1);
       Vertex v2 = new Vertex(label2);
        List<Vertex> eV1 = adjVertices.get(v1);
        List<Vertex> eV1 = adjVertices.get(v1);
        if (eV1 != null)
            eV1.remove(v2);
        if (eV2 != null)
            eV2.remove(v1);
    }
   public List<Vertex> getAdjVertices(int label) {
        return adjVertices.get(new Vertex(label));
    }
}

Python

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
#!/usr/bin/python
class Vertex:
    def __init___(self, label):
        self.label = label

    def equals(self):
        return self.data
    def hash_code(self):
        return self.data
    def get_label(self):
         return self.data
    def set_label(self, new_label):
        self.label = new_label

class Graph:
    def __init__(self, adj_vertices):
        if adj_vertices == None:
            adj_vertices = {}
        self.adj_vertices = adj_vertices

    def add_vertex(self, label):
        vertex = Vertex(label)
        if vertex not in self.adj_vertices:
            self.adj_vertices[vertex] = []

    def remove_vertex(self, label):
        vertex = Vertex(label)
        if vertex in self.adj_vertices:
            del self.adj_vertices[vertex]

    def add_edge(self, edge):
        edge = set(edge)
        (vertex1, vertex2) = tuple(edge)
        if vertex1 in self.adj_vertices:
            self.adj_vertices[vertex1].append(vertex2)
        else:
            self.adj_vertices[vertex1] = [vertex2]

    def remove_edge(self, edge):
        edge = set(edge)
        (vertex1, vertex2) = tuple(edge)
        if vertex1 in self.adj_vertices:
            del self.adj_vertices[vertex1]
        if vertex2 in self.adj_vertices:
            del self.adj_vertices[vertex2]

    def vertices(self):
        return list(self.adj_vertices.keys())

Ruby

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
#!/usr/bin/ruby
class Vertex
    attr_accessor :label
    def initialise(label)
        @label = label
    end
    def hash_code
        @label
    end
end

class Graph
    attr_accessor :adj_vertices
  def initialize()
    @adj_vertices = []
  end
  def add_vertex(label)
    @adj_vertices << Vertex.new(label)
  end
  def remove_vertex(label)
    vertex = Vertex.new(label)
    if @adj_vertices.include? vertex
        @adj_vertices.delete(vertex)
    end
  end
  def add_edge(label1, label2)
    vertex1 = @adj_vertices.index { |v| v.label == label1}
    vertex2 = @adj_vertices.index { |v| v.label == label2}
    if @adj_vertices.include? @vertex1
       @adj_vertices[@vertex1] << vertex2
    else
        @adj_vertices[@vertex1] = [vertex2]
    end
  end
  def remove_edge(label1, label2)
    vertex1 = @adj_vertices.index { |v| v.label == label1}
    vertex2 = @adj_vertices.index { |v| v.label == label2}
    if @adj_vertices.include? @vertex1
        @adj_vertices.delete(vertex1)
    end
    if @adj_vertices.include? @vertex2
        @adj_vertices.delete(vertex2)
    end
  end
  def vertices
    @vertices.length
  end
end

Javascript

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
class Vertex {
    constructor(label) {
        this.label = label;
        this.edges = {};
    }

    hasCode() {
        return this.label;
    }
}

class Graph {
    constructor(adjVertices) {
        this.adjVertices = adjVertices;
    }

    addVertex(label) {
        if(!this.adjVertices[label]) {
            this.adjVertices[label] = new Vertex(label);
        }
    }

    removeVertex(label) {
        if(this.adjVertices[label]) {
            delete this.adjVertices[val];

            Object.keys(this.adjVertices).forEach( (key, index) => {
                if(this.adjVertices[key].edges[label] ){
                    delete this.adjVertices[key].edges[val];
                }
            }).bind(this);
        }
    }

    addEdge(from, to) {
        if(this.adjVertices[from]  && this.adjVertices[to]) {
            if(this.adjVertices[from].edges[to]) {
                this.adjVertices[from].edges[to].weight +=1;
            } else {
                this.adjVertices[from].edges[to] = {weight: 1}
            }
        }
    }

    removeEdge(from, to) {
        if(this.adjVertices[from] && this.adjVertices[to]){
            if(this.adjVertices[from].edges[to]) {
                delete this.adjVertices[from].edges[to];
            }
        }
    }

    getTotalVertices(label) {
        return this.adjVertices[label];
    }
};

C++

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
#include <iostream>
using namespace std;

struct Vertex {
    int label;
    Vertex* next;
};

struct Edge {
    int from, to;
}

class Graph {

    Vertex* getAdjListNode(int to, Vertex* head) {
        Vertex* newVertex = new Vertex;
        newVertex->label = to;

        newVertex->next = head;
        return newVertex;
    }

    int N;
}

public:

    Vertex **head;

    Graph(Edge edges[], int n, int N)
    {
        head = new Vertex*[N]();
        this->N = N;

        for(int i = 0; i < N; i++)
            head[i] = nullptr;

        for(unsigned i = 0; i < n; i++)
        {
            int from = edges[i].src;
            int dest = edges[i].dest;

            Vertex* newVertex = getAdjListNode(dest, head[src]);

            head[src] = newVertex
        }
    }

PHP

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
<?php
class Vertex {
    public $label;

    function __construct($label) {
        $this->label = $label;
    }
    function getHashcode() {
        return $this->label;
    }
}
class Graph {
    private $adjVertices;
    function __construct() {
        $this->adjVertices = array();
    }
    public function addVertex($label) {
        if( !in_array($this->adjVertices, $label) ){
            $this->adjVertices[$label] = new Vertex($label)
        }
    }
    public function removeVertex($label) {
        if( in_array($this->adjVertices, $label)) {
            unset($this->adjVertices[$label])
        }
    }
    public function addEdge($label1, $label2) {
        $vertex1 = new Vertex($label1)
        $vertex2 = new Vertex($label2)

        if(in_array($this->adjVertices, $label)) {
            $this->adjVertices[$label].append($vertex2)
        } else {
            $this->adjVertices[$label] = $vertex2
        }
    }
    public function removeEdge($label1, $label2) {
        $vertex1 = new Vertex($label1)
        $vertex2 = new Vertex($label2)

        if(in_array($this->adjVertices, $label1)) {
            unset($this->adjVertices[$label])
        }
        if(in_array($this->adjVertices, $label2)) {
            unset($this->adjVertices[$label2])
        }

    }
    public function getTotalVertices() {
        return count($adjVertices)
    }
}
?>

c) Heaps

Heap

Another data structure that is commonly used. A heap is a special tree-based data structure in which the tree is a complete binary tree. Morever the tree can only be described as a complete as long as it satisfied the heap property condition such as the parent node’s key has an equal value of one of its children node’s key.

They are two main types of heaps here.

1) Max-Heap: In a max-heap, the key present at the root of the tree must be the greatest among the keys present at all of it’s children. The same property must be recursively true for all sub-trees in that same binary tree.

2) Min-Heap: In a min-heap, the key present at the root of the tree must be the lowest among the keys present at all of its children. The same property must be recursively true for all sub-trees in that same binary tree.

Here are the programming languages’ respective heaps mplementations.

Java

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
import java.util.*;

public class Heap {
    /** The number of children each node has **/
    private static final int d = 2;
    private int heapSize;
    private int[] heap;

    public BinaryHeap(int capacity)
    {
        heapSize = 0;
        heap = new int[capacity + 1];
        Arrays.fill(heap, -1);
    }

    public boolean isEmpty() {
        return heapSize  == 0;
    }

    public boolean isFull() {
        return heapSize == heap.length;
    }

    public int parent(int i) {
        return (i - 1)/ d;
    }

    private int kthChild(int i, int k) {
        return d * i + k;
    }

    public void insert(int x) {
        if(isFull())
            throw new NoSuchElementException("Overflow Exception");
        heap[heapSize++] = x;
        heapifyUp(heapSize - 1);
    }

    public int findMin() {
        if(isEmpty())
            throw new NoSuchElementException("Underflow Exception");
        return heap[0]
    }

    public int deleteMin() {
        int keyItem = heap[0];
        delete(0);
        return keyItem;
    }

    public int delete(int ind)
    {
        if (isEmpty() )
            throw new NoSuchElementException("Underflow Exception");
        int keyItem = heap[ind];
        heap[ind] = heap[heapSize - 1];
        heapSize--;
        heapifyDown(ind);
        return keyItem;
    }

    private void heapifyUp(int childInd)
    {
        int tmp = heap[childInd];
        while (childInd > 0 && tmp < heap[parent(childInd)])
        {
            heap[childInd] = heap[ parent(childInd) ];
            childInd = parent(childInd);
        }
        heap[childInd] = tmp;
    }

    private void heapifyDown(int ind)
    {
        int child;
        int tmp = heap[ ind ];
        while (kthChild(ind, 1) < heapSize)
        {
            child = minChild(ind);
            if (heap[child] < tmp)
                heap[ind] = heap[child];
            else
                break;
            ind = child;
        }
        heap[ind] = tmp;
    }

    private int minChild(int ind)
    {
        int bestChild = kthChild(ind, 1);
        int k = 2;
        int pos = kthChild(ind, k);
        while ((k <= d) && (pos < heapSize))
        {
            if (heap[pos] < heap[bestChild])
                bestChild = pos;
            pos = kthChild(ind, k++);
        }
        return bestChild;
    }
}

Python

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
#!/usr/bin/python

class Heap:
    def __init__(self):
        self.__heap = []
        self.__last_index = -1

    def push(self, value):
        self.__last_index += 1
        if self.__last_index < len(self.__heap):
            self.__heap[self.__last_index] = value
        else:
            self.__heap.append(value)
        self.__siftup(self.__last_index)

    def pop(self):
        if self.__last_index == -1:
            raise IndexError('pop from empty heap')

        min_value = self.__heap[0]

        self.__heap[0] = self.__heap[self.__last_index]
        self.__last_index -= 1
        self.__siftdown(0)

        return min_value

    def __siftup(self, index):
        while index > 0:
            parent_index, parent_value = self.__get_parent(index)

            if parent_value <= self.__heap[index]:
                break

            self.__heap[parent_index], self.__heap[index] =\
                self.__heap[index], self.__heap[parent_index]

            index = parent_index

    def __siftdown(self, index):
        while True:
            index_value = self.__heap[index]

            left_child_index, left_child_value = self.__get_left_child(index, index_value)
            right_child_index, right_child_value = self.__get_right_child(index, index_value)

            if index_value <= left_child_value and index_value <= right_child_value:
                break

            if left_child_value < right_child_value:
                new_index = left_child_index
            else:
                new_index = right_child_index

            self.__heap[new_index], self.__heap[index] =\
                self.__heap[index], self.__heap[new_index]

            index = new_index

    def __get_parent(self, index):
        if index == 0:
            return None, None

        parent_index = (index - 1) // 2

        return parent_index, self.__heap[parent_index]

    def __get_left_child(self, index, default_value):
        left_child_index = 2 * index + 1

        if left_child_index > self.__last_index:
            return None, default_value

        return left_child_index, self.__heap[left_child_index]

    def __get_right_child(self, index, default_value):
        right_child_index = 2 * index + 2

        if right_child_index > self.__last_index:
            return None, default_value

        return right_child_index, self.__heap[right_child_index]

    def __len__(self):
        return self.__last_index + 1

Ruby

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
#!/usr/bin/ruby
class Heap
  attr_accessor :heap_size, :array_rep
  def left_child(index)
    2*index + 1
  end

  def right_child(index)
    2*index + 2
  end

  def left_child_key(index)
    @array_rep[left_child(index)]
  end

  def right_child_key(index)
    @array_rep[right_child(index)]
  end
end

Javascript

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
function MinHeap() {
  this.data = [];
}

MinHeap.prototype.insert = function(val) {
  this.data.push(val);
  this.bubbleUp(this.data.length-1);
};

MinHeap.prototype.bubbleUp = function(index) {
  while (index > 0) {
    // get the parent
    var parent = Math.floor((index + 1) / 2) - 1;

    // if parent is greater than child
    if (this.data[parent] > this.data[index]) {
      // swap
      var temp = this.data[parent];
      this.data[parent] = this.data[index];
      this.data[index] = temp;
    }

    index = parent;
  }
};

MinHeap.prototype.extractMin = function() {
  var min = this.data[0];

  // set first element to last element
  this.data[0] = this.data.pop();

  // call bubble down
  this.bubbleDown(0);

  return min;
};

MinHeap.prototype.bubbleDown = function(index) {
  while (true) {
    var child = (index+1)*2;
    var sibling = child - 1;
    var toSwap = null;

    // if current is greater than child
    if (this.data[index] > this.data[child]) {
      toSwap = child;
    }

    // if sibling is smaller than child, but also smaller than current
    if (this.data[index] > this.data[sibling] && (this.data[child] == null || (this.data[child] !== null && this.data[sibling] < this.data[child]))) {
        toSwap = sibling;
    }

    // if we don't need to swap, then break.
    if (toSwap == null) {
      break;
    }

    var temp = this.data[toSwap];
    this.data[toSwap] = this.data[index];
    this.data[index] = temp;

    index = toSwap;
  }
};

C++

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
// A C++ program to demonstrate common Binary Heap Operations 
#include<iostream> 
#include<climits> 
using namespace std;

// Prototype of a utility function to swap two integers 
void swap(int *x, int *y);

// A class for Min Heap 
class MinHeap
{
    int *harr; // pointer to array of elements in heap 
    int capacity; // maximum possible size of min heap 
    int heap_size; // Current number of elements in min heap 
public:
    // Constructor 
    MinHeap(int capacity);

    // to heapify a subtree with the root at given index 
    void MinHeapify(int );

    int parent(int i) { return (i-1)/2; }

    // to get index of left child of node at index i 
    int left(int i) { return (2*i + 1); }

    // to get index of right child of node at index i 
    int right(int i) { return (2*i + 2); }

    // to extract the root which is the minimum element 
    int extractMin();

    // Decreases key value of key at index i to new_val 
    void decreaseKey(int i, int new_val);

    // Returns the minimum key (key at root) from min heap 
    int getMin() { return harr[0]; }

    // Deletes a key stored at index i 
    void deleteKey(int i);

    // Inserts a new key 'k' 
    void insertKey(int k);
};

// Constructor: Builds a heap from a given array a[] of given size 
MinHeap::MinHeap(int cap)
{
    heap_size = 0;
    capacity = cap;
    harr = new int[cap];
}

// Inserts a new key 'k' 
void MinHeap::insertKey(int k)
{
    if (heap_size == capacity)
    {
        cout << "\nOverflow: Could not insertKey\n";
        return;
    }

    // First insert the new key at the end 
    heap_size++;
    int i = heap_size - 1;
    harr[i] = k;

    // Fix the min heap property if it is violated 
    while (i != 0 && harr[parent(i)] > harr[i])
    {
       swap(&harr[i], &harr[parent(i)]);
       i = parent(i);
    }
}

// Decreases value of key at index 'i' to new_val.  It is assumed that 
// new_val is smaller than harr[i]. 
void MinHeap::decreaseKey(int i, int new_val)
{
    harr[i] = new_val;
    while (i != 0 && harr[parent(i)] > harr[i])
    {
       swap(&harr[i], &harr[parent(i)]);
       i = parent(i);
    }
}

// Method to remove minimum element (or root) from min heap 
int MinHeap::extractMin()
{
    if (heap_size <= 0)
        return INT_MAX;
    if (heap_size == 1)
    {
        heap_size--;
        return harr[0];
    }

    // Store the minimum value, and remove it from heap 
    int root = harr[0];
    harr[0] = harr[heap_size-1];
    heap_size--;
    MinHeapify(0);

    return root;
}


// This function deletes key at index i. It first reduced value to minus 
// infinite, then calls extractMin() 
void MinHeap::deleteKey(int i)
{
    decreaseKey(i, INT_MIN);
    extractMin();
}

// A recursive method to heapify a subtree with the root at given index 
// This method assumes that the subtrees are already heapified 
void MinHeap::MinHeapify(int i)
{
    int l = left(i);
    int r = right(i);
    int smallest = i;
    if (l < heap_size && harr[l] < harr[i])
        smallest = l;
    if (r < heap_size && harr[r] < harr[smallest])
        smallest = r;
    if (smallest != i)
    {
        swap(&harr[i], &harr[smallest]);
        MinHeapify(smallest);
    }
}

// A utility function to swap two elements 
void swap(int *x, int *y)
{
    int temp = *x;
    *x = *y;
    *y = temp;
}

// Driver program to test above functions 
int main()
{
    MinHeap h(11);
    h.insertKey(3);
    h.insertKey(2);
    h.deleteKey(1);
    h.insertKey(15);
    h.insertKey(5);
    h.insertKey(4);
    h.insertKey(45);
    cout << h.extractMin() << " ";
    cout << h.getMin() << " ";
    h.decreaseKey(2, 1);
    cout << h.getMin();
    return 0;
}

PHP

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
<?php
class BinaryHeap
{
    protected $heap;

    public function __construct() {
        $this->heap  = array();
    }

    public function isEmpty() {
        return empty($this->heap);
    }

    public function count() {
        // returns the heapsize
        return count($this->heap) - 1;
    }

    public function extract() {
        if ($this->isEmpty()) {
            throw new RunTimeException('Heap is empty');
        }

        // extract the root item
        $root = array_shift($this->heap);

        if (!$this->isEmpty()) {
            // move last item into the root so the heap is
            // no longer disjointed
            $last = array_pop($this->heap);
            array_unshift($this->heap, $last);

            // transform semiheap to heap
            $this->adjust(0);
        }

        return $root;
    }

    public function compare($item1, $item2) {
        if ($item1 === $item2) {
            return 0;
        }
        // reverse the comparison to change to a MinHeap!
        return ($item1 > $item2 ? 1 : -1);
    }

    protected function isLeaf($node) {
        // there will always be 2n + 1 nodes in the
        // sub-heap
        return ((2 * $node) + 1) > $this->count();
    }

    protected function adjust($root) {
        // we've gone as far as we can down the tree if
        // root is a leaf
        if (!$this->isLeaf($root)) {
            $left  = (2 * $root) + 1; // left child
            $right = (2 * $root) + 2; // right child

            // if root is less than either of its children
            $h = $this->heap;
            if (
              (isset($h[$left]) &&
                $this->compare($h[$root], $h[$left]) < 0)
              || (isset($h[$right]) &&
                $this->compare($h[$root], $h[$right]) < 0)
            ) {
                // find the larger child
                if (isset($h[$left]) && isset($h[$right])) {
                  $j = ($this->compare($h[$left], $h[$right]) >= 0)
                      ? $left : $right;
                }
                else if (isset($h[$left])) {
                  $j = $left; // left child only
                }
                else {
                  $j = $right; // right child only
                }

                // swap places with root
                list($this->heap[$root], $this->heap[$j]) =
                  array($this->heap[$j], $this->heap[$root]);

                // recursively adjust semiheap rooted at new
                // node j
                $this->adjust($j);
            }
        }
    }
}

d) Trie

Trie

In computer science, a trie is an ordered search tree that is used to store a dynamic set or associative array where the keys are usually strings. Like an ordered search tree or graph, trie is designed to determine the most efficient way of traversing and retrieving of data by mainly relying on the string prefixes.

It consists of nodes and edges much like graphs and trees. Each node consists of max 26 children and edges connect each parent node to its children. These 26 pointers are nothing but pointers for each of the 26 letters of English alphabet. A separate edge is maintained for every edge.

String are stored in a top to bottom fashion manner on the basis of their prefix in a trie. All prefixes of length 1 are stored at until level 1, all prefixes of length of 2 are stored at until level 2 and so on.

Again, here are the languages’ queue implementations.

Java

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
import java.util.Arrays;

public class Trie {
    static final int ALPHABET_SIZE = 26;

    static class TrieNode {
        TrieNode[] children = new TrieNode[ALPHABET_SIZE];

        boolean isEndOfWord;

        TrieNode() {
            isEndOfWord = false;
            for(int i =0; i < ALPHABET_SIZE; i++)
                children[i] = null;
        }
    }

    static TrieNode root;

    static void insert(String key) {
        int level;
        int length = key.length();
        int index;

        TrieNode pCrawl = root;

        for(level = 0; level < length; level++) {
            index = key.charAt(level) - 'a';

            if(pCrawl.children[index] == null)
                pCrawl.children[index] = new TrieNode();

            pCrawl = pCrawl.children[index];
        }

        pCrawl.isEndOfWord = true;
    }

    static boolean search(String key) {
        int level;
        int length = key.length();
        int index;
        TrieNode pCrawl = root;

        for(level = 0; level < length; level++) {
            index = key.charAt(level) - 'a';

            if(pCrawl.children[index] == null)
                return false;

            pCrawl = pCrawl.children[index];
        }

        return (pCrawl != null && pCrawl.isEndOfWord);
    }
}

Python

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
#!/usr/bin/python
from typing import Tuple


class TrieNode(object):
    """
    Our trie node implementation. Very basic. but does the job
    """

    def __init__(self, char: str):
        self.char = char
        self.children = []
        # Is it the last character of the word.`
        self.word_finished = False
        # How many times this character appeared in the addition process
        self.counter = 1


def add(root, word: str):
    """
    Adding a word in the trie structure
    """
    node = root
    for char in word:
        found_in_child = False
        # Search for the character in the children of the present `node`
        for child in node.children:
            if child.char == char:
                # We found it, increase the counter by 1 to keep track that another
                # word has it as well
                child.counter += 1
                # And point the node to the child that contains this char
                node = child
                found_in_child = True
                break
        # We did not find it so add a new chlid
        if not found_in_child:
            new_node = TrieNode(char)
            node.children.append(new_node)
            # And then point node to the new child
            node = new_node
    # Everything finished. Mark it as the end of a word.
    node.word_finished = True


def find_prefix(root, prefix: str) -> Tuple[bool, int]:
    """
    Check and return 
      1. If the prefix exsists in any of the words we added so far
      2. If yes then how may words actually have the prefix
    """
    node = root
    # If the root node has no children, then return False.
    # Because it means we are trying to search in an empty trie
    if not root.children:
        return False, 0
    for char in prefix:
        char_not_found = True
        # Search through all the children of the present `node`
        for child in node.children:
            if child.char == char:
                # We found the char existing in the child.
                char_not_found = False
                # Assign node as the child containing the char and break
                node = child
                break
        # Return False anyway when we did not find a char.
        if char_not_found:
            return False, 0
    # Well, we are here means we have found the prefix. Return true to indicate that
    # And also the counter of the last node. This indicates how many words have this
    # prefix
    return True, node.counter

if __name__ == "__main__":
    root = TrieNode('*')
    add(root, "hackathon")
    add(root, 'hack')

Ruby

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
#!/usr/bin/ruby
class Node
  attr_reader :data, :children
  attr_accessor :term
  def initialize(data)
    @data = data
    @children = []
    @term = false
  end

  def insert(char)
    return get(char) if have?(char)

    child = Node.new(char)
    @children << child
    child
  end

  def have?(char)
    @children.each do |c|
      return true if c.data == char
    end

    false
  end

  def get(char)
    @children.each do |child|
      return child if child.data == char
    end

    false
  end
end

class Trie
  attr_reader :root
  def initialize
    @root = Node.new(nil)
  end

  def insert(word)
    node = @root
    word.size.times do |i|
      child = node.insert(word[i])
      node = child
    end
    node.term = true
  end

  def have?(word)
    node = @root
    word.size.times do |i|
      return false unless node.have?(word[i])
      node = node.get(word[i])
    end

    return node.term == true
  end
end

Javascript

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
function Trie() {
  this.head = {
          key : ''
      , children: {}
  }
}

Trie.prototype.add = function(key) {

  var curNode = this.head
      , newNode = null
      , curChar = key.slice(0,1);

  key = key.slice(1);
  
  while(typeof curNode.children[curChar] !== "undefined"
      && curChar.length > 0){
      curNode = curNode.children[curChar];
      curChar = key.slice(0,1);
      key = key.slice(1);
  }

  while(curChar.length > 0) {
      newNode = {
              key : curChar
          , value : key.length === 0 ? null : undefined
          , children : {}
      };

      curNode.children[curChar] = newNode;

      curNode = newNode;

      curChar = key.slice(0,1);
      key = key.slice(1);
  }

};

Trie.prototype.search = function(key) {
  var curNode = this.head
      , curChar = key.slice(0,1)
      , d = 0;

  key = key.slice(1);

  while(typeof curNode.children[curChar] !== "undefined" && curChar.length > 0){
      curNode = curNode.children[curChar];
      curChar = key.slice(0,1);
      key = key.slice(1);
      d += 1;
  }

  if (curNode.value === null && key.length === 0) {
      return d;
  } else {
      return -1;
  }

}

Trie.prototype.remove = function(key) {
  var d = this.search(key);
  if (d > -1){
      removeH(this.head, key, d);
  }
}

function removeH(node, key, depth) {
  if (depth === 0 && Object.keys(node.children).length === 0){
      return true;
  }

  var curChar = key.slice(0,1);

  if (removeH(node.children[curChar], key.slice(1), depth-1)) {
      delete node.children[curChar];
      if (Object.keys(node.children).length === 0) {
          return true;
      } else {
          return false;
      }
  } else {
      return false;
  }
}

C++

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
#include <iostream>
// define character size
#define CHAR_SIZE 128

// A Class representing a Trie node
class Trie
{
public:
  bool isLeaf;
  Trie* character[CHAR_SIZE];

  // Constructor
  Trie()
  {
      this->isLeaf = false;

      for (int i = 0; i < CHAR_SIZE; i++)
          this->character[i] = nullptr;
  }

  void insert(std::string);
  bool deletion(Trie*&, std::string);
  bool search(std::string);
  bool haveChildren(Trie const*);
};

// Iterative function to insert a key in the Trie
void Trie::insert(std::string key)
{
  // start from root node
  Trie* curr = this;
  for (int i = 0; i < key.length(); i++)
  {
      // create a new node if path doesn't exists
      if (curr->character[key[i]] == nullptr)
          curr->character[key[i]] = new Trie();

      // go to next node
      curr = curr->character[key[i]];
  }

  // mark current node as leaf
  curr->isLeaf = true;
}

// Iterative function to search a key in Trie. It returns true
// if the key is found in the Trie, else it returns false
bool Trie::search(std::string key)
{
  // return false if Trie is empty
  if (this == nullptr)
      return false;

  Trie* curr = this;
  for (int i = 0; i < key.length(); i++)
  {
      // go to next node
      curr = curr->character[key[i]];

      // if string is invalid (reached end of path in Trie)
      if (curr == nullptr)
          return false;
  }

  // if current node is a leaf and we have reached the
  // end of the string, return true
  return curr->isLeaf;
}

// returns true if given node has any children
bool Trie::haveChildren(Trie const* curr)
{
  for (int i = 0; i < CHAR_SIZE; i++)
      if (curr->character[i])
          return true;  // child found

  return false;
}

// Recursive function to delete a key in the Trie
bool Trie::deletion(Trie*& curr, std::string key)
{
  // return if Trie is empty
  if (curr == nullptr)
      return false;

  // if we have not reached the end of the key
  if (key.length())
  {
      // recurse for the node corresponding to next character in the key
      // and if it returns true, delete current node (if it is non-leaf)

      if (curr != nullptr &&
          curr->character[key[0]] != nullptr &&
          deletion(curr->character[key[0]], key.substr(1)) &&
          curr->isLeaf == false)
      {
          if (!haveChildren(curr))
          {
              delete curr;
              curr = nullptr;
              return true;
          }
          else {
              return false;
          }
      }
  }

  // if we have reached the end of the key
  if (key.length() == 0 && curr->isLeaf)
  {
      // if current node is a leaf node and don't have any children
      if (!haveChildren(curr))
      {
          // delete current node
          delete curr;
          curr = nullptr;

          // delete non-leaf parent nodes
          return true;
      }

      // if current node is a leaf node and have children
      else
      {
          // mark current node as non-leaf node (DON'T DELETE IT)
          curr->isLeaf = false;

          // don't delete its parent nodes
          return false;
      }
  }

  return false;
}

// C++ implementation of Trie Data Structure
int main()
{
  Trie* head = new Trie();

  head->insert("hello");
  std::cout << head->search("hello") << " ";    // print 1

  head->insert("helloworld");
  std::cout << head->search("helloworld") << " "; // print 1

  std::cout << head->search("helll") << " ";    // print 0 (Not found)

  head->insert("hell");
  std::cout << head->search("hell") << " ";     // print 1

  head->insert("h");
  std::cout << head->search("h");                // print 1

  std::cout << std::endl;

  head->deletion(head, "hello");
  std::cout << head->search("hello") << " ";    // print 0

  std::cout << head->search("helloworld") << " "; // print 1
  std::cout << head->search("hell");             // print 1

  std::cout << std::endl;

  head->deletion(head, "h");
  std::cout << head->search("h") << " ";        // print 0
  std::cout << head->search("hell") << " ";     // print 1
  std::cout << head->search("helloworld");       // print 1

  std::cout << std::endl;

  head->deletion(head, "helloworld");
  std::cout << head->search("helloworld") << " "; // print 0
  std::cout << head->search("hell") << " ";     // print 1

  head->deletion(head, "hell");
  std::cout << head->search("hell");             // print 0

  std::cout << std::endl;

  if (head == nullptr)
      std::cout << "Trie empty!!\n";             // Trie is empty now

  std::cout << head->search("hell");             // print 0

  return 0;
}

PHP

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
<?php
class TrieNode {

    public $weight;

    private $children;

    function __construct($weight, $children) {
        $this->weight = $weight;
        $this->children = $children;
    }

    /** map lower case english letters to 0-25 */
    static function getAsciiValue($char) {
        return intval(ord($char)) - intval(ord('a'));
    }

    function addChild($char, $node) {
        if (!isset($this->children)) {
            $this->children = [];
        }
        $this->children[self::getAsciiValue($char)] = $node;
    }

    function isChild($char) {
        return isset($this->children[self::getAsciiValue($char)]);
    }

    function getChild($char) {
        return $this->children[self::getAsciiValue($char)];
    }

    function isLeaf() {
        return empty($this->children);
    }
}

That’s all for common linear-type data structures.

And that’s the end of knowing-your-algorithms-and-data-structures series in my blog post.

Hope you learn something useful out of them.

Till then. Happy Coding!

Comments