## Data Structures Notes

Data Structures Basic

Stacks

Queues

Linked List

Sorting

Tree

Graphs

Hashing and Searching

# Heading

Q

1

What do you understand by Minimum spanning tree?

Ans

The cost of the spanning tree is the sum of the weights of all the edges in the tree. There can be many spanning trees. Minimum spanning tree is the spanning tree where the cost is minimum among all the spanning trees. There also can be many minimum spanning trees.

Minimum spanning tree has direct application in the design of networks. It is used in algorithms approximating the travelling salesman problem, multi-terminal minimum cut problem and minimum-cost weighted perfect matching.

Q

2

What is binary search tree? Explain with example?

Ans

1.A binary tree is a non-linear data structure which is a collection of elements called nodes.

2.In a binary tree, the topmost element is called the root-node. An element can have 0,1 at the most 2 child nodes.

3.There are many variants of Binary tree. A Binary search tree or BST is one among them.

4.A binary search tree, also known as ordered binary tree is a binary tree wherein the nodes are arranged in a order. The order is :

a) All the values in the left sub-tree has a value less than that of the root node.

b) All the values in the right node has a value greater than the value of the root node.

c) The same rule is carried forward to all the sub-tree in tree.

5.Since the tree is already ordered, the time taken to carry out a search operation on the tree is greatly reduced as now we don’t have to traverse the entire tree, but at every sub-tree we get hint where to search next.

6.Binary trees also help in speeding up the insertion and deletion operation.

7.The average running time of a search operation is O(log2 n ) as at every step, the search-area is reduced by half.

Consider an example. We need to insert the following elements in a binary tree:

48,2,98,12,56,32,4,6

1.Firstly we insert the first element as the root node.

2.Then we take the next element in queue a check whether it is lesser or greater than root node.

3.Here it will go to left tree as 2 is less than 48.

4.Then the third value, i.e 98 will go to right tree as 98 is greater than 48. And so on we progress

Q

3

What is splay tree?

Ans

A splay tree is a binary search tree with the additional property that recently accessed elements are quick to access again. Like self-balancing binary search trees, a splay tree performs basic operations such as insertion, look-up and removal in O(log n) amortized time. For many sequences of non-random operations, splay trees perform better than other search trees, even performing better than O(log n) for sufficiently non-random patterns, all without requiring advance knowledge of the pattern.

Q

4

Write down the code to implement binary tree?

Ans

Java code:

import java.util.LinkedList;

import java.util.Queue;

public class BinaryTree {

//Represent a node of binary tree

public static class Node{

int data;

Node left;

Node right;

public Node(int data){

//Assign data to the new node, set left and right children to null

this.data = data;

this.left = null;

this.right = null;

}

}

//Represent the root of binary tree

public Node root;

public BinaryTree(){

root = null;

}

//insertNode() will add new node to the binary tree

public void insertNode(int data) {

//Create a new node

Node newNode = new Node(data);

//Check whether tree is empty

if(root == null){

root = newNode;

return;

}

else {

Queue<Node> queue = new LinkedList<Node>();

//Add root to the queue

queue.add(root);

while(true) {

Node node = queue.remove();

//If node has both left and right child, add both the child to queue

if(node.left != null && node.right != null) {

queue.add(node.left);

queue.add(node.right);

}

else {

//If node has no left child, make newNode as left child

if(node.left == null) {

node.left = newNode;

queue.add(node.left);

}

//If node has left child but no right child, make newNode as right child

else {

node.right = newNode;

queue.add(node.right);

}

break;

}

}

}

}

//inorder() will perform inorder traversal on binary search tree

public void inorderTraversal(Node node) {

//Check whether tree is empty

if(root == null){

System.out.println("Tree is empty");

return;

}

else {

if(node.left!= null)

inorderTraversal(node.left);

System.out.print(node.data + " ");

if(node.right!= null)

inorderTraversal(node.right);

}

}

public static void main(String[] args) {

BinaryTree bt = new BinaryTree();

//Add nodes to the binary tree

bt.insertNode(1);

//1 will become root node of the tree

System.out.println("Binary tree after insertion");

//Binary after inserting nodes

bt.inorderTraversal(bt.root);

bt.insertNode(2);

bt.insertNode(3);

//2 will become left child and 3 will become right child of root node 1

System.out.println("\nBinary tree after insertion");

//Binary after inserting nodes

bt.inorderTraversal(bt.root);

bt.insertNode(4);

bt.insertNode(5);

//4 will become left child and 5 will become right child of node 2

System.out.println("\nBinary tree after insertion");

//Binary after inserting nodes

bt.inorderTraversal(bt.root);

bt.insertNode(6);

bt.insertNode(7);

//6 will become left child and 7 will become right child of node 3

System.out.println("\nBinary tree after insertion");

//Binary after inserting nodes

bt.inorderTraversal(bt.root);

}

}

Output:

Binary tree after insertion

1

Binary tree after insertion

2 1 3

Binary tree after insertion

4 2 5 1 3

Binary tree after insertion

4 2 5 1 6 3 7

Q

5

What is expression tree and expression manipulation?

Ans

The expression tree is a binary tree in which each internal node corresponds to the operator and each leaf node corresponds to the operand so for example expression tree for 3 + ((5+9)*2) would be

Inorder traversal of expression tree produces infix version of given postfix expression (same with postorder traversal it gives postfix expression)

Evaluating the expression represented by an expression tree:

Let t be the expression tree

If t is not null then

If t.value is operand then

Return t.value

A = solve(t.left)

B = solve(t.right)

// calculate applies operator 't.value'

// on A and B, and returns value

Return calculate(A, B, t.value)