Tree Archives - SimpleTechTalks

Binary Search Tree data structures explained

A Binary Search Tree is a Binary tree in which all the nodes have following properties.

Left subtree of a node contains all the nodes having values lesser than the node.
Right subtree of a node contains all the nodes having values higher than the node.
Both the left and right subtree is also a Binary Search Tree.

As the name suggests, this data structure is mainly used for faster searching. In order to do that, restrictions are applied while inserting/deleting an element into the tree. As a result of these restrictions, worst case search time complexity remains at O(log n).

Below are some examples of Binary Search Trees.

(more…)

Binary Tree data structures explained

by admin

Tree data structures are 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.

Below are some examples of Binary Tree.

(more…)

Boundary Traversal Of A Binary Tree

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.

Boundary traversal of a binary tree, traverses through all the boundary nodes which includes

The left boundary of a binary tree
All the leaves of the binary tree
The right boundary of a binary tree

Before going ahead have a look into Binary Tree basics, Binary Tree Traversal and Binary Tree implementation.

(more…)

Program To Find the Lowest Common Ancestor In Binary Tree

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.
The lowest common ancestor of any two nodes X and Y in a binary tree is the lowest node in tree that has both X and Y node as successor.
Before going ahead have a look into Binary Tree basics, Binary Tree Traversal and Binary Tree implementation.

(more…)

Program to Convert Binary Tree to Sum Tree

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…)

Program To Check if a Binary Tree is a Sum Tree

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…)

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…)

Maximum Heap Explained With Simple Example

by admin

A Maximum Heap is a binary tree which has following properties:

Binary tree MUST be a complete binary tree which means all leaf nodes are present in either at height “h” or “h-1”.
Key stored in each node is smaller than or equal to keys in the node’s children.

Before going ahead, have a look into Binary Tree.

(more…)