**Data Structure Reference Material and Study Material**

**1.Data Structures ( a pseudocode approach with c++)**

**2. Data Structure and algorithm made easy**

**3. Cracking coding interview**

**4. GeeksforGeeks**

**5. Google Group**

**googlegeeks**~~algogeeks~~

**6.**

**CareerCup**

**7. IIT DELHI DataStructure**

**8. Standford Data Structure**

**Class**

**9. Book**

10. Good Basic information

**11. Hash Table Tutorial**

**http://www.ziddu.com/download/12665791/notes_17.pdf.html**- http://note-for-it.blogspot.com/2008/11/algorithms-data-structures-hashing.html

**12. Hashing function**

13.

**Hash Info**

**http://www.algolist.net/Data_structures/Hash_table**- http://www.doctorinterview.com/A.html
- http://www.codeguru.com/forum/archive/index.php/t-386222.html

15.

**Heap Sort**

16. Data Structure Source Code

18.

20.

21.

if we make a restriction that each node can have maximum two children we can have binary tree.

The definiation: a binary tree as a tree which is either empty or consists of a root node together

with two binary tree a left subtree and right subtree of the root.

A

/ \

B C

The definition given above is a recursive definition where an empty binary tree is a base case

which allows the recursion loop.

A binary tree with a single node is a binary tree with a root whose left and right subtrees are empty.

if there are two nodes in the binary tree one will be root and other can be the left child or

the right child of the root.

A C

/ or \

B D

A binary tree is called a strictly binary tree if every nonleaf node in the binary tree has nonempty

left and right subtree.

This means each node in a binary tree will have either 0 or 2 children.

A strictly binary tree with n leaves always contain exactly 2n-1 nodes.

A complete binary tree can be defined as a binary tree whose nonleaf nodes have non empty

left and right subtree and all leaves are at the same level.

A

/ \

B C

/ \ / \

D E F G

If a binary tree has the property that all elements in the left subtree of a node n are less than

the contents of n and all elements in the right subtree are greater than the content of n

such a binary tree is called binary search tree.

As the name suggest they are very useful for searching an element just as with binary search.

A binary search tree is a binary tree which is either empty or contains a node whose key

statisfies the condition:

a) The key in the left child of a node (if any) precees the key in the parent node

b) The key in the right child of a node (if any) suceesds the key in the parent node

c) The left and right subtree of the root are again binary search tree.

we are assuming that there are no duplicates which means that no two entries in binary

search tree can have equal keys.

Tree node may be implemented as array element or as dynamically allocated variables.

Each node of a tree contains info left and right field.

Using the array implemenation we may declare

#define maxnum 100

struct nodetree {

int info;

int left;

int right;

}

struct nodetree node[maxnum];

here we can refer to the info,left and right field of a node as a node[p].info,

node[p].left and node[p].right respectively.

This representation is called as linked array represenation.

we can also define a node as

struct nodetree

{

int info;

struct nodetree *left,*right;

}tree;

struct nodetree *p;

Now the fileds info left right of a node p can be referred as p->info,

p->left and p->right respectively. This representation is called the dynamic node

representation of binary tree.

To search the tree we use a traversal pointer p and set it equal to the root of the tree. Then we comparethe info field of p with the given value. if the info is equal to x we exit the routine and return the current value of p. if the x is less than info p we search in the left subtree of p otherwise we search in the right

subtree by making p equal to p->right we continue searching untill we have found the desire value or reach the end of the tree.

Another important operation is to create and maintain a binnary search tree. A new node

will always be inserted at its proper position in the binary search tree as a leaf

While inserting any node we have to take that the resulting tree statisfie the properties of

binary search tree.

A new node will always be inserted at the proper position in the binary search tree as a leaf.

Before writing a routine for inserting a node let us see how a binary tree may be

created for following input.

10,15,12,7,8,18,6,20

First of all we must initialize the tree . To create an empty tree we must initialize root to null.

The first node will be inserted into the tree as a root.

10

/ \

7 15

/ \ / \

6 8 12 18

\

20

To find the insertion place for the new value we initialize temporary pointer p which point to the root node we can change p to move left and right through the tree as we did for searching

a particular value in the tree.

When p becomes null it is not possible to the link new node at this position becuase there is no

access to the node p was pointing to just before it became null.

P become null when we have found that 17 will be inserted at the left of 18 so we need a way to climb back into the tree so that we can access node cotaining 18 in order to make its left

pointer point to node 17

We must therefore need a pointer which points to a node cotaining 18 when p becomes null

To achieve this we have another pointer which must follow p as it moves through the tree

When p become null this pointer will point to the leaf node to which we will the new node

The algorithum to insert a new node is as follows.

/* get a new node and make it a leaf

getnode(q);

left(q)=null;

right(q)=null;

info(q)=x;

/* Initialize the traversal pointer */

p=root

trail =null

/* search for the insertion place */

while p<>null do

begin

trail =p

if info(p)> x

then p=left(p)

else p=right(p)

end

/* To adjust the pointer*/

if trail =null

then root =q

else

if info(trail) >X

then left(trail) =q

else right(trail)=q

The insertion algorithum can be coded into a C routine.There are two parameters

which msut be passed to this routine.

one is tree and other is the value to be inserted x.

tree insert(s,x)

int x;

tree *s;

{

tree *trail,*p,*q;

q=(tree*) malloc(sizeof(tree));

q->info =x;

q->left =null;

q->rigth =null;

p =s;

trail =null;

while(p!=null)

{

trail =p;

if(p->info >x)

p=p>left

else

p=p->right;

}

if trail ==null

{

s=q;

return (s);

}

if(info(trail)>x)

left(trail)=q;

else

right(trail)=q;

return(s);

}

Another important function for maintaining binary search tree is to delete a specific

node from the tree. The method to delete a node depends on the specific position

of the node in the tree.

if the node to be deleted is a leaf, we only need to set the appropiate link of its parent

to nil and dispose of the node which is deleted.

if the node to be deleted has only one child we can not make the link of the parent

to nil as we have done in the case of leaf becuase if we do so we will loose all of the

descendants of the node which we are deleting from the tree.

so we need to adjust the link from the parent of the deleted node to the point to the

child of the node we intend to delete.

The most complicated problems comes when we have to delete a node with two

children.

There is no way we can make the parent of the deleted node to point to both

of the children of the deleted node.

So we attach one of the subtree of the nodes to be deleted to the parent and then

hang the other subtree onto the appropriate node of the first sub tree

Let us attach right subtree to the parent node of the right subtree since every key

in the left subtree is less than every key in the right subtree.

Therefore we must attach the left subtree as far to the left as possible.

For example we want to delete x.

r

/ \

q x

/ \

t y

/ \ \

s u z

if we delete node containing x we make parent of x to point to the right

subtree and then go as far as left possible and attach the left subtree there

To understand in better way let us look at some more examples of these type of deletion

void delete (p)

struct tree *p;

{

struct tree *temp;

if(p==null)

cout<<" trying to delete a non existent"<<endl;

else if ( p->left ==null)

{

temp =p;

p=p->right;

free(temp);

}

else if( p-> right ==null)

{

temp =p;

p=p->left;

free(temp);

}

else if( p->left != NULL && p->right !=NULL)

{

temp =p->right;

while(temp ->left !=null)

temp= temp ->left;

temp->left = p->left;

temp=p;

p=p->right;

free(temp);

}

Notice that the while loop stop stop when it finds a node with an empty left subtree

and not when it finds an empty subtree itself. So that the left subtree of the node to be deleted

can be attached here.

Also note that we first attach the left subtree at the proper plcae and then attach the right

subtree to the parent of the node to be deleted.

Some more info

http://www.algolist.net/Data_structures/Binary_search_tree/Removal

Another useful operation on a binary tree is a traversal which is to move all the nodes

of the binary tree visiting each one in turn for example to print all of the values in the tree

At a given order, there are three things to do in the some order.To visit the node itself

to traverse its left subtree and to taverse its right subtree.

Depending on the whether we traverse the node itself before traversing either subtree

between the subtree or after traversing both subtrees there are many orders in which

we can traverse all the nodes

Depending of the position at which the given node or the root is visited the name is given

if the root is visited before traversing its subtree it is called the pre order traversal

if the root is visited after traversing its subtree it is called the post order traversal

if the root is visited in between the subtree it is called in order traversal

A

/ \

B C

Pre Order -->(root,left,right) ABC

Post Order --> (left,right,root) BCA

In Order ---> (left,root,right) BAC

Wiki Pages : http://en.wikipedia.org/wiki/Tree_traversal

Some info about Tree : http://nptel.iitm.ac.in/courses/Webcourse-contents/IIT-%20Guwahati/data_str_algo/frameset.htm

Very Good Exersize for tree traversal

http://nova.umuc.edu/~jarc/idsv/

void inorder(p);

struct tree *p

{

if(p!=NULL)

{

inorder(p->left)

printf("%c,p->info);

inorder(p->right);

}

}

void preorder(p)

struct tree *p

{

if(p!=NULL)

{

printf("%c,p->info);

preorder(p->left);

preorder(p->right);

}

}

void postorder(p)

struct tree *p;

{

if(p!=NULL)

{

postorder(p->left);

postorder(p->right);

printf("%c",p->info);

}

}

http://neural.cs.nthu.edu.tw/jang/courses/cs2351/slide/animation/Level%20Order%20Traversal%20of%20a%20Binary%20Tree.pps

http://www.thecareerplus.com/?page=resources&cat=10&subCat=75&qNo=12

What is hashing or hash function?

Producing hash value for for accesing data.A hash value also call message digest is a number

generated from hash function. A hash function will generate a unique key value to search data.

A hash search is a search in which the key,through an algorithum function determines the location of

the data.

we use a hashing algo to transform the key into the index that contain the data we need to locate.

Sorting wiki Page

- http://comet.lehman.cuny.edu/stjohn/teaching/algLehman/heap.html
- http://cis.stvincent.edu/html/tutorials/swd/heaps/heaps.html

**17.****Algorithum for Power of two**18.

**Software Interview Puzzle****19**. Linked List20.

**Tusor video (Data structure for beginner)**21.

**Bipartite**

if we make a restriction that each node can have maximum two children we can have binary tree.

The definiation: a binary tree as a tree which is either empty or consists of a root node together

with two binary tree a left subtree and right subtree of the root.

A

/ \

B C

The definition given above is a recursive definition where an empty binary tree is a base case

which allows the recursion loop.

A binary tree with a single node is a binary tree with a root whose left and right subtrees are empty.

if there are two nodes in the binary tree one will be root and other can be the left child or

the right child of the root.

A C

/ or \

B D

A binary tree is called a strictly binary tree if every nonleaf node in the binary tree has nonempty

left and right subtree.

This means each node in a binary tree will have either 0 or 2 children.

A strictly binary tree with n leaves always contain exactly 2n-1 nodes.

A complete binary tree can be defined as a binary tree whose nonleaf nodes have non empty

left and right subtree and all leaves are at the same level.

A

/ \

B C

/ \ / \

D E F G

If a binary tree has the property that all elements in the left subtree of a node n are less than

the contents of n and all elements in the right subtree are greater than the content of n

such a binary tree is called binary search tree.

As the name suggest they are very useful for searching an element just as with binary search.

A binary search tree is a binary tree which is either empty or contains a node whose key

statisfies the condition:

a) The key in the left child of a node (if any) precees the key in the parent node

b) The key in the right child of a node (if any) suceesds the key in the parent node

c) The left and right subtree of the root are again binary search tree.

we are assuming that there are no duplicates which means that no two entries in binary

search tree can have equal keys.

**Binary Tree Representations**Tree node may be implemented as array element or as dynamically allocated variables.

Each node of a tree contains info left and right field.

Using the array implemenation we may declare

#define maxnum 100

struct nodetree {

int info;

int left;

int right;

}

struct nodetree node[maxnum];

here we can refer to the info,left and right field of a node as a node[p].info,

node[p].left and node[p].right respectively.

This representation is called as linked array represenation.

we can also define a node as

struct nodetree

{

int info;

struct nodetree *left,*right;

}tree;

struct nodetree *p;

Now the fileds info left right of a node p can be referred as p->info,

p->left and p->right respectively. This representation is called the dynamic node

representation of binary tree.

**Operation on binary tree**To search the tree we use a traversal pointer p and set it equal to the root of the tree. Then we comparethe info field of p with the given value. if the info is equal to x we exit the routine and return the current value of p. if the x is less than info p we search in the left subtree of p otherwise we search in the right

subtree by making p equal to p->right we continue searching untill we have found the desire value or reach the end of the tree.

*search(p,x)**int x;**struct tree *p;**{**p=root;**while(p!=NULL && p->info !=x)**{**if(p->info >x)**p =p->left;**else**p->right;**}**return p;**}***Insertion into a Tree**Another important operation is to create and maintain a binnary search tree. A new node

will always be inserted at its proper position in the binary search tree as a leaf

While inserting any node we have to take that the resulting tree statisfie the properties of

binary search tree.

A new node will always be inserted at the proper position in the binary search tree as a leaf.

Before writing a routine for inserting a node let us see how a binary tree may be

created for following input.

10,15,12,7,8,18,6,20

First of all we must initialize the tree . To create an empty tree we must initialize root to null.

The first node will be inserted into the tree as a root.

10

/ \

7 15

/ \ / \

6 8 12 18

\

20

To find the insertion place for the new value we initialize temporary pointer p which point to the root node we can change p to move left and right through the tree as we did for searching

a particular value in the tree.

When p becomes null it is not possible to the link new node at this position becuase there is no

access to the node p was pointing to just before it became null.

P become null when we have found that 17 will be inserted at the left of 18 so we need a way to climb back into the tree so that we can access node cotaining 18 in order to make its left

pointer point to node 17

We must therefore need a pointer which points to a node cotaining 18 when p becomes null

To achieve this we have another pointer which must follow p as it moves through the tree

When p become null this pointer will point to the leaf node to which we will the new node

The algorithum to insert a new node is as follows.

/* get a new node and make it a leaf

getnode(q);

left(q)=null;

right(q)=null;

info(q)=x;

/* Initialize the traversal pointer */

p=root

trail =null

/* search for the insertion place */

while p<>null do

begin

trail =p

if info(p)> x

then p=left(p)

else p=right(p)

end

/* To adjust the pointer*/

if trail =null

then root =q

else

if info(trail) >X

then left(trail) =q

else right(trail)=q

The insertion algorithum can be coded into a C routine.There are two parameters

which msut be passed to this routine.

one is tree and other is the value to be inserted x.

tree insert(s,x)

int x;

tree *s;

{

tree *trail,*p,*q;

q=(tree*) malloc(sizeof(tree));

q->info =x;

q->left =null;

q->rigth =null;

p =s;

trail =null;

while(p!=null)

{

trail =p;

if(p->info >x)

p=p>left

else

p=p->right;

}

if trail ==null

{

s=q;

return (s);

}

if(info(trail)>x)

left(trail)=q;

else

right(trail)=q;

return(s);

}

**Deletion from a binary search tree**Another important function for maintaining binary search tree is to delete a specific

node from the tree. The method to delete a node depends on the specific position

of the node in the tree.

if the node to be deleted is a leaf, we only need to set the appropiate link of its parent

to nil and dispose of the node which is deleted.

if the node to be deleted has only one child we can not make the link of the parent

to nil as we have done in the case of leaf becuase if we do so we will loose all of the

descendants of the node which we are deleting from the tree.

so we need to adjust the link from the parent of the deleted node to the point to the

child of the node we intend to delete.

The most complicated problems comes when we have to delete a node with two

children.

There is no way we can make the parent of the deleted node to point to both

of the children of the deleted node.

So we attach one of the subtree of the nodes to be deleted to the parent and then

hang the other subtree onto the appropriate node of the first sub tree

Let us attach right subtree to the parent node of the right subtree since every key

in the left subtree is less than every key in the right subtree.

Therefore we must attach the left subtree as far to the left as possible.

**This proper place can be found by going left untill an empty left subtree is found**For example we want to delete x.

r

/ \

q x

/ \

t y

/ \ \

s u z

if we delete node containing x we make parent of x to point to the right

subtree and then go as far as left possible and attach the left subtree there

To understand in better way let us look at some more examples of these type of deletion

void delete (p)

struct tree *p;

{

struct tree *temp;

if(p==null)

cout<<" trying to delete a non existent"<<endl;

else if ( p->left ==null)

{

temp =p;

p=p->right;

free(temp);

}

else if( p-> right ==null)

{

temp =p;

p=p->left;

free(temp);

}

else if( p->left != NULL && p->right !=NULL)

{

temp =p->right;

while(temp ->left !=null)

temp= temp ->left;

temp->left = p->left;

temp=p;

p=p->right;

free(temp);

}

Notice that the while loop stop stop when it finds a node with an empty left subtree

and not when it finds an empty subtree itself. So that the left subtree of the node to be deleted

can be attached here.

Also note that we first attach the left subtree at the proper plcae and then attach the right

subtree to the parent of the node to be deleted.

Some more info

http://www.algolist.net/Data_structures/Binary_search_tree/Removal

**Tree Traversals**Another useful operation on a binary tree is a traversal which is to move all the nodes

of the binary tree visiting each one in turn for example to print all of the values in the tree

At a given order, there are three things to do in the some order.To visit the node itself

to traverse its left subtree and to taverse its right subtree.

Depending on the whether we traverse the node itself before traversing either subtree

between the subtree or after traversing both subtrees there are many orders in which

we can traverse all the nodes

Depending of the position at which the given node or the root is visited the name is given

if the root is visited before traversing its subtree it is called the pre order traversal

if the root is visited after traversing its subtree it is called the post order traversal

if the root is visited in between the subtree it is called in order traversal

A

/ \

B C

Pre Order -->(root,left,right) ABC

Post Order --> (left,right,root) BCA

In Order ---> (left,root,right) BAC

Wiki Pages : http://en.wikipedia.org/wiki/Tree_traversal

Some info about Tree : http://nptel.iitm.ac.in/courses/Webcourse-contents/IIT-%20Guwahati/data_str_algo/frameset.htm

Very Good Exersize for tree traversal

http://nova.umuc.edu/~jarc/idsv/

void inorder(p);

struct tree *p

{

if(p!=NULL)

{

inorder(p->left)

printf("%c,p->info);

inorder(p->right);

}

}

void preorder(p)

struct tree *p

{

if(p!=NULL)

{

printf("%c,p->info);

preorder(p->left);

preorder(p->right);

}

}

void postorder(p)

struct tree *p;

{

if(p!=NULL)

{

postorder(p->left);

postorder(p->right);

printf("%c",p->info);

}

}

- Preorder traversal sequence: F, B, A, D, C, E, G, I, H (root, left, right)
- Inorder traversal sequence: A, B, C, D, E, F, G, H, I (left, root, right); note how this produces a sorted sequence
- Postorder traversal sequence: A, C, E, D, B, H, I, G, F (left, right, root)
- Level-order traversal sequence: F, B, G, A, D, I, C, E, H

**Level Oder traversal**:http://neural.cs.nthu.edu.tw/jang/courses/cs2351/slide/animation/Level%20Order%20Traversal%20of%20a%20Binary%20Tree.pps

http://www.thecareerplus.com/?page=resources&cat=10&subCat=75&qNo=12

**Some Pratical use**- http://stackoverflow.com/questions/2130416/what-are-the-applications-of-binary-trees
- http://stackoverflow.com/questions/1698564/binary-trees-usage

**Hashing:**What is hashing or hash function?

Producing hash value for for accesing data.A hash value also call message digest is a number

generated from hash function. A hash function will generate a unique key value to search data.

**Hash seacrh?**A hash search is a search in which the key,through an algorithum function determines the location of

the data.

we use a hashing algo to transform the key into the index that contain the data we need to locate.

**Binary tree info****video lecture**- http://nptel.iitm.ac.in/video.php?courseId=1074

**Theory****Data Structure Lecture & BookC**

**Advantage of B-tree:**

Advantages of B-Tree indices:

n May
use less tree nodes than a corresponding B

^{+}-Tree.
n Sometimes
possible to find search-key value before reaching leaf node.

Disadvantages of B-Tree indices:

n Only
small fraction of all search-key values are found early

n Non-leaf
nodes are larger, so fan-out is reduced.
Thus B-Trees typically have greater depth than corresponding

B

B

^{+}-Tree
n Insertion
and deletion more complicated than in B

^{+}-Trees
n Implementation
is harder than B

^{+}-Trees.
Limitation B-Tree:

B+ Tree:

**Sorting Analysis**

Sorting wiki Page

**HeapSort**- http://en.wikipedia.org/wiki/Heapsort

**Bucket Sort**

**Suffix Tree****Trie**and

**Trie Tutorial**

**Trie implementation**

**Dynamic Programming Tutorial**

**Dynamic Programming****dynamic-programming-and-memoization-bottom-up-vs-top-down-approaches****what-is-the-difference-between-memoization-and-dynamic-programming?noredirect=1&lq=1****Dynamic Programming**

**Merge Sort**

**Recursion**