Data Structures Archives - Page 2 of 10

Program To Check if a Binary Tree is a Sum Tree

A tree is a data structure similar to Linked list in which each node points to multiple nodes instead of simply pointing to the next node. A tree is called Binary tree if each node in a tree has maximum of two nodes.
An empty tree is also a Binary tree. We can call the two children of each node as Left and Right child of a node. The node of the tree which has no parent is called the Root of the tree. Perhaps Binary tree is the most used tree data structure in the programming world. Before going ahead have a look into Binary Tree basics, Binary Tree Traversal and Binary Tree implementation.

(more…)

Program to Check Whether a Binary Tree is Symmetric

by admin

A tree is a data structure similar to Linked list in which each node points to multiple nodes instead of simply pointing to the next node. A tree is called Binary tree if each node in a tree has maximum of two nodes.
An empty tree is also a Binary tree. We can call the two children of each node as Left and Right child of a node. The node of the tree which has no parent is called the Root of the tree. Perhaps Binary tree is the most used tree data structure in the programming world. Before going ahead have a look into Binary Tree basics, Binary Tree Traversal and Binary Tree implementation.

(more…)

Autocomplete Feature Using Trie Explained With Simple Example

by admin

Autocomplete is a feature to suggest possible words to a partially typed string. This feature is widely used by most applications such as – Google, Bing, IDEs etc. To support auto complete feature, Trie data structure is used to maintain a dictionary and based on those suggestions can be made.

A trie is a N-ary tree data structure for storing strings in order to support fast string search. Tries can insert or search the string in O(L) time where L is length of string. Trie is mainly used in cases where dictionary kind of data structure needs to be maintained.

Assuming the dictionary contains all the strings were made of all small alphabets “a” to “z” then each node of the trie will have 26 pointers, one for each character.

(more…)

Trie Data Structure Basics and Implementation Explained With Simple Example

by admin

A trie is a N-ary tree data structure for storing strings in order to support fast string search. Tries can insert or search the string in O(L) time where L is length of string. Trie is mainly used in cases where dictionary kind of data structure needs to be maintained.

Assuming the dictionary contains all the strings were made of all small alphabets “a” to “z” then each node of the trie will have 26 pointers, one for each character. Let’s have a look into simple trie data structure definition.

#define LETTER_LENGTH 26
class Trie
{
    public:
        Trie* m_ptr[LETTER_LENGTH];
        bool is_word_complete;
        Trie ();
};
Trie::Trie ()
{
    for (int i = 0; i < LETTER_LENGTH; i++)
    {
        m_ptr[i] = NULL;
    }
}

(more…)

Adding Two Numbers Represented by Linked List

by admin

Given 2 numbers where each digit is represented by a Linked List, write a program to sum the numbers and save it in a third Linked List.
For eg:

List 1 = 7 -> 8 -> 6 -> 4
List 2 = 6 -> 6 -> 8 -> 4 -> 6
—————————————-
Sum = 7-> 4 -> 7 -> 1 -> 0

(more…)

Bellman Ford’s Shortest Path Algorithm

by admin

Shortest path algorithms are designed to find the minimum cost path between two nodes in a graph. This algorithm can be used to find out the fastest way to reach from one place to another or it can be used to find cheapest way to fly or travel between source and destination.
A weighted graph is a graph in which every edge is not of same weight. In this weighted graph, we have to find the shortest path to all the vertices from a given vertices.
Before going ahead have a look into Graph Basics.

(more…)

Dijsktra Shortest Path Algorithm Explained with Simple Example

by admin

Shortest path algorithms are designed to find the minimum cost path between two nodes in a graph. This algorithm can be used to find out the fastest way to reach from one place to another or it can be used to find cheapest way to fly or travel between source and destination.
A weighted graph is a graph in which every edge is not of same weight. In this weighted graph, we have to find the shortest path to all the vertices from a given vertices.
Before going ahead have a look into Graph Basics.

(more…)

Shortest path in unweighted graph explained with simple example

by admin

Shortest path algorithms are designed to find the minimum cost path between two nodes in a graph. This algorithm can be used to find out the fastest way to reach from one place to another or it can be used to find cheapest way to fly or travel between source and destination.
An unweighted graph is a graph in which all the edges are of same cost. In this unweighted graph, we have to find the shortest path to all the vertices from a given vertices. This algorithm is very much similar to BFS.
Before going ahead have a look into Graph Basics.

(more…)

Connected Graph Property Explained With Simple Example

by admin

Graph is a data structure which consists of a set of vertices which is called as Node, together with a set of collection of pair of vertices which is called as an Edge.
A graph data structure can be represented as a pair (V, E) where V is a set of nodes called vertices and E is a collection of pairs of vertices called edges. Graphs are used to solve many real-life problems such as fastest ways to go from A to B etc.

A Graph is called connected graph if each of the vertices of the graph is connected from each of the other vertices which means there is a path available from any vertex to any other vertex in the Graph.

Before going ahead have a look into Graph Basics.

(more…)

Topological Sort Explained With Simple Example

by admin

Topological sort is a method to sort the vertices in directed acyclic graph in which each node comes before all the nodes to which it has edges going to. Topological sort is mainly used in cases where a certain node can be visited if and only if certain nodes has been visited before.

A Directed Acyclic graph or DAG is a graph which doesn’t have any cycle.

All pairs of consecutive vertices in topological sorted order are connected by edges which forms a directed Hamiltonian Path.

(more…)