What are the missing data structures in Collections (Java, JavaScript and Python)?

Programming languages such as Java, JavaScript and Python provides APIs for many data structures such as Arrays, Map and Set. They are very handy for us to use. But there are missing data structures in collections that are widely used, but not provided. The developers have to write their own implementations for these data structures, such as Binary tree, nary tree, Trie and graph. In JavaScript, we have to write our own Priority queue.

In this post, the implementations of Binary tree, Graph and Trie are provided. They share a same feature – consists of nodes. The implementation includes common methods such as add, delete, search and traverse.

Table of Content


1. Binary tree

A tree is a collection of nodes connected by edges. Each node points to a number of nodes. A binary tree has at most two children, we name them left child and right child.

binary-tree

To implement binary tree, first we fine a TreeNode. Then we define the BinaryTree class. It has attributes of root. There are 4 kinds of operations: add, delete, search (DFS), traversal (inorder, preorder and postorder). To delete, you can choose to promote left child or right child as successor. Click binary tree for complete implementation and download.

Java

JavaScript

Python


2. Graph

A graph contains a set of nodes and edges. Nodes are used to store and retrieve data. The nodes are also called vertices. Edges are used to connect nodes. In our implementation, we first define class GraphNode, in which it defines the node information and its neighbors.

graph diagram

In Graph class, we define the basic operations, such as addNode, addEdge, search and traverse. For graph traversal, there are two ways – DFS and BFS. Depth First Search (DFS): It starts from the source node, and explores the adjacent nodes as far as possible before backtracking. DFS is usually implemented with recursion or stack. Breath First Search (BFS): It starts from the source node, and explores all its adjacent nodes before going to the next level adjacent nodes. BFS is usually implemented with Queue.


3. Trie

A trie  is a tree-like data structure in which every node stores a character. After building the trie, strings or substrings can be retrieved by traversing down a path of the trie.

trie diagram

In this implementation, we use array to link to the children nodes. First, we define TrieNode. It contains the information of the node and its children. If a node is the last character of the string, isEnd is true. Otherwise it is false. In Trie class, we have implementation of methods add, delete, search and print. Print is to print all strings in trie, using recursion. Click trie for complete implementation and download.

Java

JavaScript

Python

More data structures implementation in Java, JavaScript, Python and Doodle
Data structures and Java collections
Java coding interview questions series (YouTube)

Comments are closed