Trees (Data Structures): Two Marks Important Questions and Answers

Data Structures using C ++

Chapter 6: Trees

Two Marks Questions with Answers

1. Give various implementation of tree.

Answer:

The tree can be implemented by two ways

1. Sequential implementation ‒ The tree is implemented using arrays in this type of implementation.

2. Linked implementation ‒ The tree is implemented or represented using linked list.

2. Define : Binary tree.

Answer:

A binary tree is a finite set of nodes which is either empty or consists of root and two disjoint binary trees called the left subtree and right subtree.

3. Define complete binary tree.

Answer:

A complete binary tree is a tree in which every node except the leaf nodes should have exactly two children not necessarily on the same level.

4. How is binary tree represented using an array ? Give an example.

Answer:

In an array root node will be at position 1. Its left child will be at position 2 and right child will be at position 3. Hence the nodes of tree are placed in array using following formula ‒

Parent (n) = floor (n‒1)/2

left (n) = (2n + 1)

right (n) = (2n + 2)

Consider tree as given below.

It will be placed in an array as given below.

5. Define binary search tree.

Answer:

Binary search tree is a binary tree in which each node is systematically arranged i.e. the left child has less value than its parent node and right child has greater value than its parent node. The searching of any node in such a tree becomes efficient in this type of tree.

For example ‒

6. Which tree representation is mostly preferred by the developers Sequential or linked? Justify.

Answer:

There are two ways of representing the binary tree ‒ and linked representation. The linked representation is normally preferred by sequential representation developers because in the linked representation the binary tree is represented using linked list. Hence the tree with any number of nodes can be created. Secondly there is no wastage or shortage of the memory in this representation.

7. State the properties of binary search tree.

Answer:

Following are some important properties of binary search tree ‒

1. The left node should contain the key value which is less than its parent node's key value.

2. The right node should have the key value which is greater than its parent node's key value.

3. Both the left and right subtrees must also be binary search trees.

8. When does a binary tree become binary search tree?

Answer:

If the node containing the value less than the value of the parent node is attached as a left child and a node containing the value greater than the value of the parent node is attached as a right child then that binary tree becomes the binary search tree. Refer Fig. 6.7.1.

9. When the tree is called complete binary tree?

Answer:

The complete binary tree is a full binary tree in which every node has zero or two children and all the leaves are at the same depth.

10. Why it said that the searching a node in a binary search tree is efficient than that of a simple binary tree?

Answer:

In the binary search tree the nodes are arranged in such a way that the left node is having less data value than rot node value. And the right nodes are having larger value than that of root. Because of this while searching any node the value of target node will be compared with the parent node and accordingly either left sub branch or right sub branch will be searched. This procedure will be repeated if required. So one has to compare only particular branches. Thus searching becomes efficient.

11. What is the time complexity of binary search tree?

Answer:

The time complexity of binary search tree is n log₂n.

12.  List the applications of trees.

Answer:

In computer networking such as Local Area Network (LAN), Wide Area Networking (WAN), internetworking.

2. In telephone cabling graph theory is effectively used.

3. In job scheduling algorithms the graphs are used.

13. In tree construction which is the suitable efficient data structure ?

Answer:

The linked list is the efficient data structure for constructing the trees. Because using linked list there is no wastage of memory or shortage of memory. The nodes can be allocated or deallocated as per the requirements.

14. Find the maximum number of nodes in complete binary tree if d is the depth.

Answer:

The maximum number of nodes in a complete binary tree with depth d are 2^d+1 ‒ 1. For example ‒ If the depth of a complete binary tree d = 2, then total number of nodes are: 2²⁺¹ – 1 = 7

15. In the given binary tree, using array(the index starts from 1), you can store the node 4 at ‒‒‒‒‒‒‒‒‒position? How?

Answer:

The node 4 is stored at 5^th position because the array representation of tree is ‒

16. Consider following tree on deleeing 7, draw the resultant tree structure.

Answer:

On deleting a node with two child nodes, its place is replaced by its inorder successor. Hence the resultant tree structure will be ‒

17. A binary search tree is created by inserting following integers ‒ 50, 14, 65, 5, 20, 57, 91, 3, 8, 37, 60, 25. Mention the number of nodes in left and right subtree.

Answer:

The binary search tree will be ‒

Number of nodes in left subtree = 7

Number of nodes in right subtree= 4

18. What is a tree?

Answer:

i) There is a specially designated node called root.

ii) The remaining nodes are partitioned into n>=0 disjoint sets T₁, T₂, T₃, ..... ‚T_n

where T₁, T₂, T₃, ...,T_n are called the sub‒trees of the root.

19. Draw expression tree for (a + b * c) + ((de + f) * g).

Answer:

The expression tree is as follows:

20. What are the two ways of representing binary tree?

Answer:

The two ways of representing a binary tree are

1. Sequential representation

2. Linked representation