Two Mark Questions…
1) Define Binary Tree
Binary tree is a finite set of elements that is either empty or is partitioned into three disjoint subsets- The root, left subtree and right subtree.
2) What is a father node, and left and right sons?
If A is the root of a binary tree and B is the root of its left or right subtree, then A is said to be the father of B and B is said to be the left or right son of A.
3) What is a leaf node?
The node that do not have any sons is called leaf node.
4) Define the term ancestor.
Node n1 is said to be the ancestor of node n2, if n1 is either the father of n2 or father of some ancestor of n2.
5) Define the term descendent.
Node n2 is said to be the descendant of node n1, if n2 is either the left or right son of node n1 or son of some descendant of n1.
6) Define the term left descendant
A node n2 is the left descendant of node n1, if n2 is either the left son of n1 or a descendant of the left son of n1.
7) Define the term right descendant.
A node n2 is the right descendant of node n1, if n2 is either the right son of n1 or a descendant of the right son of n1.
8) Define the term brothers.
Two nodes are brothers if they are the left and right sons of the same father.
9) What is a strictly binary tree?
The binary tree in which every nonleaf node has nonempty left and right subtrees, is called a strictly binary tree. (Include a diagrammatic example)
10) Define level of a binary tree.
The level of a binary tree is defined as, The root of the tree has level 0, and the level of any other node in the tree is one more than the level of its father.
11) Define Depth.
The depth of a binary tree is the maximum level of any leaf in the tree. This is same as the length of the longest path from the root to any leaf.
12) What is a complete binary tree.
A complete binary tree of depth d is the strictly binary tree all of whose leaves are at level d.
13) What si a almost complete binary tree?
A binary tree of depth d is an almost complete binary tree if:
i) Each leaf in the tree is either at level d or level d-1.
ii) For any node nd in the tree with the right descendant at level d, all the left descendants that are leaves should also be at level d.
14) How almost complete binary tree nodes can be numbered?
The nodes in almost complete binary tree are numbered so that, the root is assigned the number 1, and the left son is assigned a number twice that of its father, and the right son is one more than twice the number assigned to its father. (give example diagram)
15) What are the basic operations on a binary tree?
Let p be a pointer to a node and x be the information. Now, the basic operations are:
i) info(p)
ii) father(p)
iii) left(p)
iv) right(p)
v) brother(p)
vi) isleft(p)
vii) isright(p)
viii) maketree(x)
ix) setleft(p,x)
x) setright(p,x)
16) What is traversal. What are the types of traversal?
Traversal means visiting of nodes. There are three types of traversal
i) Preorder (depth-first order)
ii) Postorder
iii) Inorder (symmetric order)
17) Explain the steps for Depth-first order traversal.
Visit the root
Traverse the left subtree
Traverse the right subtree.
18) Explain the steps for Symmetric order traversal.
Traverse the left subtree
Visit the root
Traverse the right subtree.
19) Explain the steps for postorder traversal.
Traverse the left subtree
Traverse the right subtree.
Visit the root
20) What is a binary search tree.
A binary tree in which all the elements in the left subtree of a node n are less than the contents of n, and all the elements in the right subtree of n are greater than or equal to the contents of n is called a binary search tree.
21) What are internal nodes and external nodes?
The non leaf nodes are called internal nodes where as leaf nodes are called external nodes.
22) What are the methods to indicate the non existent nodes in a binary tree, when a sequential representation is made?
One way is to use negative numbers as null indicators in a positive binary tree.
Another way is to use a used field to indicate whether the node is in use or not.
23) How can you say recursive procedure is efficient than non recursive?
There is no extra recursion
The automatic stacking and unstacking make it more efficient
There is no extraneous parameters ans local variables used.
24) What is a thread?
Thread is a pointer from the right field of leaf node to its inorder successor.
25) What is a right-in-threaded binary tree?
The right field of each leaf node other than the right most leaf node, if it has pointer to the next inorder successor, we call it as a right in-threaded binary tree.
26) What is a left in-threaded binary tree?
A left in-threaded binary tree is one in which each NULL left pointer is altered to contain a thread to that node’s inorder predecessor.
27) Define left and right pre-threaded binary tress.
Left and right prethreaded binary trees can be defined as the binary trees in which th null pointers of the nodes are replaced by their preorder succcessors and predecessors.
28) What are Heterogeneous binary trees?
Heterogeneous binary trees are the binary trees whose nodes may contain different data types. (eg: Binary tree representation of expressions- Draw a diagram)
29) What are \Huffman trees?
Huffman trees are the trees which are generated with the frequency of each alphabet for encoding a message in bit string format.
30) What is a tree?
A tree is a finite nonempty set of elements in which one element is called the root and the remaining elements are partitioned into m>=0 disjoint subsets, each of which is itself a tree. Each element in a tree is called node.
31) What is a ordered tree?
A ordered tree is defined as a tree in which the subtrees of each node form an ordered set.The first son of the ordered tree is the oldest son of that node, and the last son as youngest.
32) Define the term forest.
Forest is an ordered set of ordered trees.
Other questions:
1) Write the algorithm for creating a binary search tree, which eliminate duplicates.
2) What is the advantage of linear array representation of binary tree over dynamic node representation?
3) What is the advantage of dynamic node representation of binary tree over linear array representation ?
4) Write the procedure for maketree(x).
5) Write the procedure for setleft(p,x).
6) Write the procedure for setright(p,x).
7) What are the disadvantage of using the same representation for leaf nodes and non leaf nodes? How could they be rectified?
8) Write the procedure for sequential representation of a binary tree.
9) Write the recursive procedure for inorder, postorder and preorder traversals of binary tree.
10) Write the non recursive procedure for inorder traversal in a binary tree.
11) Write the procedure for traversing the right in-threaded binary tree.
12) Explain Huffman algorithm in Detail (16)
13) Write the procedure for finding the Kth element in a Binary tree representation of List.
14) Write the procedure for deleting an element in a Binary tree representation of List.
15) What are the application of trees?
Works for you….
1) If there are m nodes in a binary tree at level l, then there can be atmost 2m nodes at level l+1. Is this statement true or false. State the reason.
2) Derive the equation to find the total number of nodes in a complete binary tree.
3) If the total number of nodes in a complete binary tree is 15, what is the depth of the binary tree?
4) If the depth of a complete binary tree is 9, what is the totall number of nodes in it?
5) Only one almost complete binary tree can be drawn with n nodes. Is this statement true or false. If false, give two alternate representations for an almost complete binary tree with 10 nodes.
6) Create a binary search tree for the following list of numbers.
13, 12, 56, 8, 4 ,78, 7, 2, 9, 34, 22
7) Create a binary search tree for the following list of numbers and write the inorder, postorder and preorder traversal results.
15,9,18,5,4,17,14,6,7,21,33
8) Represent the expression (A+B*C)$((A+B)*C) using binary tree and write the inorder, postorder and preorder traversal results.
