.png)
Mobiprep has created last-minute notes for all topics of Tree to help you with the revision of concepts for your university examinations. So let’s get started with the lecture notes on Tree.
Our team has curated a list of the most important questions asked in universities such as DU, DTU, VIT, SRM, IP, Pune University, Manipal University, and many more. The questions are created from the previous year's question papers of colleges and universities.
Tree
Question 1 - What do you understand by Minimum spanning tree?
Answer - 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.
Question 2 - What is binary search tree? Explain with example?
Answer -
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 :
All the values in the left sub-tree has a value less than that of the root node.
All the values in the right node has a value greater than the value of the root node.
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
Firstly we insert the first element as the root node.
Then we take the next element in queue a check whether it is lesser or greater than root node.
Here it will go to left tree as 2 is less than 48.
Then the third value, i.e 98 will go to right tree as 98 is greater than 48. And so on we progress.
Question 3 - What is splay tree?
Answer - 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.
Question 4 - Write down the code to implement binary tree?
Answer - 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 7Question 5 - What is expression tree and expression manipulation?
Answer - 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)