CS301 Midterm Solved Subjective with References by Moaaz and Awais

Q1. What is complete binary tree?

Answer: "A complete binary tree is a binary tree with the additional property that every node must have exactly two children if an internal node, and zero children if a leaf node."

Q2. How single left rotation is performed in AVL tree?

Answer: This rotation is almost similar to the single right rotation. We start from tree node k1. k1 is the root whilet ree node k2 is its right child. Due to the left rotation, the right child k2 of the root k1 will become the root. The k1 will go down to the left child of k2.

Q3. describe the following

Answer: (Page 209) The height of a binary tree is the maximum level of its leaves (also called the depth).

Answer: (page 215) The balance of a node in a binary search tree is defined as the height of its left subtree minus height of its right subtree. In other words, at a particular node, the difference in heights of its left and right subtree gives the balance of the node.

Q1. what is binary tree brief it?

Answer: “A binary tree is a finite set of elements that is either empty or is partitioned into three disjoint subsets. The first subset contains a single element called the root of the tree. The other two subsets are themselves binary trees called the left and right sub-trees”.

Q2. what is different between binary tree and AVL tree

Answer: (Page 212) An AVL tree is identical to a BST, barring the following possible differences:

•  Height of the left and right subtrees may differ by at most 1.
•  Height of an empty tree is defined to be (–1).

Answer: (Page 87) A queue is a linear data structure into which items can only be inserted at one end and removed from the other. In contrast to the stack, which is a LIFO (Last In First Out) structure, a queue is a FIFO (First In First Out) structure.

How we can delete a node with two Childs in a binary search tree using its right sub tree.

Answer: Page 263 The node to be deleted has either left child (subtree) or right child (subtree).In this case we bypass the node in such a way that we find the inorder successor of this node and then link the parent of the node to be deleted to this successor node. Thus the node was deleted.

define const keyword, reference variable, Dangling reference

Answer: (Page 198)

Const keyword

The const keyword is used for something to be constant. The actual meanings depend on where it occurs but it generally means something is to held constant. There can be constant functions, constant variables or parameters etc.

Reference variable

The references are pointers internally, actually they are constant pointers. You cannot perform any kind of arithmetic manipulation with references that you normally do with pointers.

Dangling reference

The pointer of the object (when object has already been deallocated or released) is called dangling pointer.

Q1. what is complete binary tree?

Answer: (Page 123) The definition of the complete binary tree is A complete binary tree of depth d is the strictly binary tree all of whose leaves are level d.

Q2. how single left rotation is performed in AVL tree?

Answer: rep

Q3. describe the following

Answer: rep

Q1. what is binary tree breif it?

Answer: rep

Q2. what is different between binary tree and AVL tree

Answer: rep

Answer: rep

1. What is function of length () method in the Queue

Answer: (page 111) In Queue length() method, has a single statement i.e. return size ; This method returns the size of the queue, reflecting the number of elements in the queue. It is not the size of the array used internally to store the elements of the queue.

2. Explain the two cases in which we apply double rotation in An Avl tree

Answer: (Page 229) Sometimes a single rotation is not sufficient to balance an unbalanced tree. The two cases are following:

1. Insertion into the right subtree of the left child of X node (RL)
2. Insertion into the left subtree of the right child of X node (LR)

Q3. How can we perform level-order traversal on a tree?

Answer: (For More detail and code see Page 161 ) We can print a binary tree level by level by employing recursive or non-recursive method. The idea of a level-order traversal is to visit the root, then visit all nodes "1 level away" (depth 2) from the root (left to right), then all nodes "2 levels away" (depth 3) from the root, etc. For the example tree, the goal is to visit the nodes in the following order:

A level-order traversal requires using a queue (rather than a recursive algorithm, which implicitly uses a stack). A queue is a FIFO structure, which can make the level-order traversal easier.

Q4. How can the dangling reference problem be avoided?

Answer: ( Page 200 ) To avoid dangling reference, don’t return the reference of a local variable (transient) from a function.

Q1. What is complete binary tree?

Answer: rep

Q2. How single left rotation is performed in AVL tree?

Answer: rep

What is binary tree breif it?

Answer: rep