Implement binary search tree with parent pointer

Binary search tree with parent feature

A binary search tree is a type of ordered binary tree, where the left child has a value smaller than its parent, and the right child has a value greater than or equal to its parent. In a binary search tree, a node has two references, the left child and …

Continue reading

Implement circular queue using an array

circular queue

A circular queue is a queue in which all elements are connected to form a circular. A circular queue can be implemented with an array or a linked list. In the array implementation, the index of the rear element wraps around to the beginning of the array. In this post, …

Continue reading

Implement priority queue using an array

A priority queue is a queue in which you insert an element at the back (enqueue) and remove an element from the front (dequeue). Meanwhile, a priority queue is a special queue, the element with the highest priority shall be dequeued first. You can implement a priority queue using an …

Continue reading

Implement graph as adjacency list

graph feature

A graph is a data structure that consists of a set of nodes connected by edges. Graphs are used to simulate many real-world problems, such as paths in cities, circuit networks, and social networks. This post is to implement a graph as an adjacency list. Table of Content Terminology Add node and …

Continue reading

Shortest path from source to destination in matrix – Code

shortest path in matrix

Shortest path in matrix is to find the shortest distance from the the source to the destination. As you know, graph can be represented as adjacent matrix. Therefore, we can use the Breadth First Search algorithm in graph to solve this problem. BFS starts from the source node. It explores …

Continue reading

Autocorrect with trie and edit distance in Java

autocorrect java

Google provides a powerful autocorrect for validating the keywords we type into the input text box. It checks against a dictionary. If it doesn’t find the keyword in the dictionary, it suggests a most likely replacement. To do this it associates with every word in the dictionary a frequency, the …

Continue reading

Shortest path and 2nd shortest path using Dijkstra – code

shortest path using Dijkstra java

Dijkstra’s algorithm is an algorithm to find the shortest paths between vertices in a graph. It uses greedy technique by picking the un-visited vertex with the lowest distance. When all vertices have been evaluated, the result is the shortest path. This post provides code to find shortest path and second …

Continue reading

Build hierarchy tree – Code

build hierarchy tree listing

Build hierarchy tree reads employee data and build a corporation hierarchy tree from the list. HashMap plays important role to store the data when reading the input. The trick of this question is to find the root. You can get the root by finding the employee without the manager. Starting …

Continue reading

Depth first search in matrix using recursion

DFS and adjacent matrix

An adjacency matrix is a 2d array representing a graph. The nodes are the headings for the rows and columns. The element in the cell indicates whether an edge is present between two nodes. Depth first search (DFS) is an algorithm used to traverse or search in a graph. The …

Continue reading

Permutation of multiple arrays and iterator – code

permutation

Permutation of multiple arrays and iterator has two tasks. First is the permutation of multiple arrays and output as an array of new combinations. The second is to implement the iterator of this new array. Permutation is an important topic in the fields of combinatorics. It is usually implemented using …

Continue reading