For each of the following trees determine whether or not the

For each of the following trees, determine whether or not the tree is a binary tree, a two-tree, full, and complete and give reasons for your determinations. If there is a subtree that does meet the criteria for the categories above, list the nodes of the subtree. For each tree state: the height, the number of nodes, the number of external nodes, and the number of internal nodes. For trees I and II perform a traversal of each of the following types: inorder, postorder, preorder, and level order.

Solution

1. Binary Tree : A tree is called binary tree if each node has 0 child, 1 child or 2 children.

2. Strict Binary Tree : A binary tree is called strict binary tree if each node has exactly two children or no children

3. Full Binary Tree ( 2- Tree or Proper Binary Tree) : A binary tree is called full binary tree if each node has excatly 2 children and all the leaf nodes are at same level.

4. compleate Binary tree : A complete binary tree is a binary tree in which every level, except possibly the last, is completely filled, and all nodes are as far left as possible.

5. Nodes with no children are called leaves, or external nodes.

6. Nodes which are not leaves are called internal nodes.

7. inorder traversal : left subtree->root -> right subtree

8. postorder traversal : left subtree -> right subtree-> root.

9. preorder traversal : root -> left subtree -> rightsubtree .

Q a) :

1 st one is binary tree Since it has each node has 0 or 1 or 2 child node(s).

2nd one is Strict binary tree since each node has 2 children or no children and leaf nodes are not at same level.

3rd one is generic-tree Since it has more than 2 nodes. root has 3 children. and each siblings has 3,2, 2 children again and etc..

4th one is complete binary tree.

Q b ) : Assume that root node is at Height zero.

1. height : 3 no. of nodes: 11 no.of internal nodes: 6 no. of external nodes: 5

2. height : 3 no. of nodes: 9 no.of internal nodes: 4 no. of external nodes: 9

3. height : 4 no. of nodes: 18 no.of internal nodes: 10 no. of external nodes: 8

4. height : 4 no. of nodes: 14 no.of internal nodes: 7 no. of external nodes: 7

Q c) :

1. inorder : 4,5,6,8,10,11,17,19,31,43,49

   postorder: 5,4,10,8,6,17,31,49,43,19,11

   preorder: 11,6,4,5,8,10,19,17,43,31,49

    levelorder : 11, 6, 19 , 4, 8, 17 , 43 , 5, 10, 31 , 49

2 . inorder: a ,- ,b ,/ ,c ,+ ,d ,* ,e

    postorder: a, b, c, /, - , d, e , * , +

    preorder : +, - , a , /, b, c, *, d, e

    levelorder: +, -, *, a, /, d, e, b, c