Q. No.
Question Marks TL CO
Define i) Binary tree ii) Binary search tree
Answer:
1 i) Binary Tree: A hierarchical data structure where each node has at most two children called left child and right child. 2 R CO6
ii) Binary Search Tree (BST): A special binary tree in which for every node: all elements in the left subtree are smaller, and all elements in the right
subtree are larger than the node’s key.
State the following term. i) Leaf node of a tree ii) Degree of a tree
Answer:
2 2 R CO6
i) Leaf node: A node with no children (outdegree = 0).
ii) Degree of a tree: The maximum number of children any node in the tree has.
Traverse the following tree by the in-order and pre-order.
3 2 U CO6
Answer:
In-order sequence(Left → Root → Right)
D, B, A, E, G, C, H, F, I
Pre-order sequence(Root → Left → Right)
A, B, D, C, E, G, F, H, I
Define the term w.r.t. tree. i) In-degree ii) Out-degree
Answer:
4 2 U CO6
i) In-degree of a node: The number of edges coming into a node (for trees, always 1 except root which has 0).
ii) Out-degree of a node: The number of edges going out from a node (equal to number of children of that node).
Construct the Binary Search Tree using following elements (35,15,40,7,10,100,28,82,53,25,3). Show diagrammatically
each step of construction of BST.
Answer:
Insert elements one by one:
1) 35 → root.
2) 15 < 35 → left child of 35.
3) 40 > 35 → right child of 35.
4) 7 < 15 → left child of 15.
5) 10 > 7 → right child of 7.
6) 100 > 40 → right child of 40.
7) 28 > 15 & < 35 → right child of 15.
8) 82 < 100 → left child of 100.
5 9) 53 < 82 → left child of 82. 4 A CO6
10) 25 < 28 → left child of 28.
11) 3 < 7 → left child of 7.
Final BST Diagram (text form):
35
/ \
15 40
/ \ \
7 28 100
/ \ / /
3 10 25 82
/
53
6 From the given tree, complete the following answers. (i) Degree of tree (ii) Degree of node B (iii) Level of node H (iv) In- 4 U CO6
degree of node C (v) Outdegree of node B (vi) Height of the tree.
Answer:
(i) Degree of tree: 3 (max children at any node — node B has 3)
(ii) Degree of node B: 3 (children: D, E, F)
(iii) Level of node H: 3 (A=level 1 → A→C→H)
(iv) Indegree of node C: 1 (one edge comes into C from A)
(v) Outdegree of node B: 3 (children: D, E, F)
(vi) Height of the tree: 3 (longest root-to-leaf path in edges; e.g., A→B→E→I or A→C→G→K)
Write algorithm for preorder traversal of binary tree.
Answer:
Algorithm (Preorder TBT):
1) Visit root.
2) Recursively traverse left subtree (preorder).
3) Recursively traverse right subtree (preorder).
C Function (recursive):
void preorder(struct node* root)
7 4 A CO6
{
if(root!=NULL)
{
printf("%d ", root->data);
preorder(root->left);
preorder(root->right);
}
}
Explain Binary Search Tree with example.
Answer:
A Binary Search Tree is a special type of binary tree in which:
1. Each node has at most two children → left and right.
2. For every node:
o All the values in its left subtree are smaller than the node’s value.
o All the values in its right subtree are greater than the node’s value.
This property holds recursively for every subtree in the tree.
8 Example: Insert {50,30,70,20,40,60,80}. 4 A CO6
BST diagram (text):
50
/ \
30 70
/\ /\
20 40 60 80
Properties:
(i) Inorder traversal of BST always gives sorted sequence,
(ii) Searching is efficient (O(log n) in average case).
9 Traverse the following tree by the in-order, pre-order and post-order methods. 4 A CO6
Answer:
In-order Traversal (Left → Root → Right)
H, D, I, B, E, J, A, F, C, G, K
Pre-order Traversal (Root → Left → Right)
A, B, D, H, I, E, J, C, F, G, K
Post-order Traversal (Left → Right → Root)
H, I, D, J, E, B, F, K, G, C, A
Differentiate between general tree and binary tree.
Answer:
General Tree:
1) Node can have any number of children.
2) No fixed structure for degree.
3) Traversals less standardized.
10 4) Used for file system directories, organization charts. 4 A CO6
Binary Tree:
1) Node can have at most two children.
2) Left and right subtrees defined.
3) Traversals standardized: inorder, preorder, postorder.
4) Used in BST, heaps, expression trees.
Course Coordinator Module Coordinator
