Binary Search Tree [CS62 june 2001]

Queation: 1.(c) Define binary search tree. Write a function in C to creat a binary search tree.

Answer: A binary search has porperty that all elements in the left subtree of a node n are less than the contents of n and alll elements in the sight subtree of n are greater than or equal to the contents of n.
If a binary search tree is traversed in inorder (left, root, sight) and the contents of each node are printed as the node is visited, the numbers as the node is visited, the numbers are printed in ascending order.

q=null;
p=tree;
while(p!=null){
if (key ==k(p))
return(p);
q=p;
if(key < key(p))
p=left(p);
else
p=right(p);
}
v=maketree(rec,key);
if(q==null)
tree=v;
else
if(key < k(q))
left(q)=v;
else
right(q)=v;
return(v);

IGNOU BCA MCA

CS-62 JUNE 2003 QNO 3(c)

3 (c) What is an AVL tree? How does it differ from a Binary Tree?
Answer

A Tree is called AVL tree (Balanced Binary tree) if each node possesses one of the following properties:
(i) A node is called left heavy, if the longest path in its left subtree is one longer then the longest past of its right subtree.
(ii) A node is called right heavy, if the longest part in the right subtree is one longer than the longest path in its left subtree.
(iii) a node is called balanced if the longest paths in both the right and the left subtrees are equal.

Binary tree: A tree is a binary tree if each node of it can have at the most two branches. In other words we can say that if every node of a tree can have at most degree two, then its is called binary tree. In a binary tree left and right subtrees distinguish subtrees of a node.

An AVL tree is a balanced tree, but binary tree can be unbalanced also.

CS-62 JUNE 2003 QNO 2(a)

QuestionDraw the internal memory representation of the following Binary Tree using Sequential Representation. Assume that nodes appear in the following physical sequence:

A, B, C, D, E, G, F, H


Answer

Index	0	1	2	3	4	5	6	7	8	9	10	11
Value	A	B	C	D	E	G			F			H

CS-62 JUNE 2003 QNO 1(c)

Question: Write a function that takes only a pointer to the root of a binary tree T and computes the number of nodes in T.

Answer: When we traverse a binary tree then all the nodes of tree should traversed. Now if we put a pointer as a counter than it will print the total no of nodes. Any of the traversal schemes can be used to determine the number of elements in abinery tree. But we can use this mechanism also to count the total no. of neds of left subtree and right subtree.
The function is as follows:
int TotalNodes(bnodes*tree)
{
if(tree==(bnode*true)NULL)
return 0;
else
return (TotalNodes(tree->left)+TotalNodes(tree->right)+1);
}