Page 119 - DCAP605_ADVANCED_DATA_STRUCTURE_AND_ALGORITHMS

Advanced Data Structure and Algorithms

Notes 2. How many binary trees are possible with three nodes?

3. Construct a binary tree whose in-order and pre-order traversal is given below.
In-order: 5,1,3,11,6,8,4,2,7
Pre-order: 6,1,5,11,3,4,8,7,2
4. What do you mean by binary tree? Also explain the various properties of binary tree.
5. Consider the tree given below:
(a) Find the degree of each mode of the tree.

(b) The degree of the tree.
(c) The level of each nodes of the tree.

50

35 49

24 30 27 40 45

12 18 22 37 39 43

6. Determine the order in which the vertices of the binary tree given in question No. 1 will be
visited under:
(a) Inorder
(b) Preorder
(c) Postorder

7. Write a C program to delete all the leaf nodes of a binary tree.
8. Write a method and the corresponding recursive function to count the leaves (i.e., the
nodes with both subtrees empty) of a linked binary tree.
9. Write a method and the corresponding recursive function to insert an Entry, passed as a
parameter, into a linked binary tree. If the root is empty, the new entry should be inserted
into the root, otherwise it should be inserted into the shorter of the two subtrees of the root
(or into the left subtree if both subtrees have the same height).
10. Write a function to perform a double-order traversal of a binary tree, meaning that at each
node of the tree, the function first visits the node, then traverses its left subtree (in double

order), then visits the node again, then traverses its right subtree (in double order).
Answers: Self Assessment

1. (d) 2. (b)
3. (a) 4. (b)

5. number of children for the node to be deleted

114 LOVELY PROFESSIONAL UNIVERSITY