Tag: Tree

Interview Questions / Tree

Trie Data Structure Basics and Implementation Explained With Simple Example

adminby 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…)
Trie Data Structure Basics and Implementation Explained With Simple Example Read More
Binary Tree / Interview Questions / Programming Questions / Tree

Binary Tree explained with simple example

adminby 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.

(more…)
Binary Tree explained with simple example Read More