Tree: Data Structure Class Notes

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

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.

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 :

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

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.

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 7

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)