Tree's , Basics for Algorithms

Tree's

Basics to Algorithm Part 1

After getting to know what algorithms are, we move on forward to know how to design and  analyse different algorithms but as to write some words we need prior knowledge of alphabets, to write sentences we need prior knowledge of words, Similarly for design and analysis of algorithms we need to know about various Data structures. Today we will be Learning a data structure known as Trees. As the name suggest a tree is something similar to which we see as hierarchical tree, one root gives birth to some children and those children nodes gives birth to more children and this cycle continues , This type of structure is known as a tree data structure. 

A tree is a data structure made up of nodes or vertices and edges without having any cycle. The tree with no nodes is called the null tree. A tree that is not empty consists of a root node and potentially many levels of additional nodes that form a hierarchy. as shown below in fig(a)

fig(a)

As we can see in fig(a), Tree consists of a root, child,  siblings and leaf nodes . 

Root node: the node after which all the other children nodes is derived is known as a root node.

Child: A node which is directly connected to another node when moving away from the root node or parent node.

Sibling node: Nodes with same parents are known as sibling nodes.

Binary Tree

fig(b)

Binary tree are a special kind of tree with each node having at most 2 children. Binary tree is an important type of data structure which is commonly used.

Sequential Binary Tree

fig(c)

A Sequential binary tree is a kind of tree with the data stored sequentially. ie. as in fig(c), the data 

0,1,9,5,4,8,12 

is stored as 

0

1 , 9

(5,4) , (8,12)

as represented in fig(c).

Binary Search Tree

fig(d)

Binary Search Trees are another special kind of Binary trees in which data is stored as, all the 

elements less than parent node to the left of it, and all the elements greater than or equal to parent node to the right of the parent node.

For storing the array of data elements in a binary search tree [5,0,2,4,10,9,12]

Step 1: Root node = 5

Step 2: 0 < 5 , hence put 0 to the left of 5.

Step 3: 2 < 5 & 2 > 0, hence put 2 to the right of 0 which is left of 5 (refer fig(d)).

Step 4: 4 < 5 & 4 > 0 & 4 > 2, hence put 4 to the right of 2( in tree left of 0) .

Step 5: 10  > 5, hence put 10 to the right of 5.

Step 6: 9 > 5 & 9 < 10 . Hence put 9 to the left of 10 which is in the right subtree of 5.

Step 7: 12 > 5 & 12 > 10, Put 12 to the right of 10 in the right subtree.

Written by, Sarvesh Bhatnagar.