DSA QB Solution
5th Module ( 2 Marks Questions)
85. Differentiate Tree and Graph
Basis Tree Graph
Hierarchical structure with parent–child Network structure with nodes connected
Structure
relationship. arbitrarily.
Cycles No cycles are allowed. Cycles may exist.
Edges Has exactly (n – 1) edges for n nodes. Can have any number of edges (≥ n–1).
Root
Always has a single root node. No concept of a root node.
Node
Traversed using pre, post, or in-order
Traversal Traversed using DFS or BFS algorithms.
methods.
86. Discuss Binary Tree and Binary Search Tree
1. A Binary Tree allows each node to have at most two children.
2. A Binary Search Tree (BST) is a type of binary tree with ordered structure.
3. In BST: Left < Root < Right property is maintained.
4. BST allows efficient searching, insertion, and deletion operations.
87. Explain the properties of Binary Search Tree
1. The left subtree contains nodes with values less than the root.
2. The right subtree contains nodes with values greater than the root.
3. No duplicate values are allowed in a BST.
4. In-order traversal of BST gives sorted order of elements.
88. Define Tree data structure and list its types
1. A Tree is a non-linear hierarchical data structure made up of nodes connected by edges.
2. The topmost node is called the root.
3. Common types include General Tree, Binary Tree, Binary Search Tree, AVL Tree,
and Heap.
4. Used in file systems, expression trees, and hierarchical databases.
89. Organize below data to form Binary Tree and Binary Search Tree and list all
leaf nodes
Data: 40, 36, 49, 35, 38, 51, 39
Binary Tree (simple insertion order):
40 → 36 → 49 → 35 → 38 → 51 → 39
Binary Search Tree (BST order):
40
/ \
36 49
/ \ \
35 38 51
\
39
Leaf Nodes: 35, 39, 51
90. Complete the below logic of Post Order Tree Traversal
void postOrder(struct Node *root)
{
if(root != NULL)
{
postOrder(root->left);
postOrder(root->right);
printf("%d ", root->data);
}
}
91. State advantages of In-order Tree Traversal Technique
1. In BST, in-order traversal gives elements in sorted (ascending) order.
2. It visits left → root → right nodes in logical order.
3. Helps in converting tree data into a sorted list or array.
4. Used in operations like searching, printing, and checking order property of BST.
Module 5 (5 Marks Questions)
93. What is a Tree? Explain Expression Tree with an example
Definition:
1. A Tree is a non-linear hierarchical data structure consisting of nodes connected by
edges.
2. The topmost node is called the root.
3. Each node may have zero or more child nodes.
4. It is widely used to represent hierarchical relationships like organization charts, file
systems, and expressions.
Expression Tree:
1. An Expression Tree is a binary tree used to represent arithmetic expressions.
2. Internal nodes represent operators (+, -, *, /).
3. Leaf nodes represent operands (numbers or variables).
4. It helps in evaluating, converting, and parsing expressions.
Example Expression:
Infix Expression → (A + B) * (C - D) *
/\
Corresponding Expression Tree: Blue Box
+ -
Traversal Type Expression Result
/\/\
In-order (A + B) * (C - D)
A BC D
Pre-order *+AB-CD
Post-order AB+CD-*
94. What is a Binary Search Tree (BST)? Construct BST with given nodes and
show steps.
Definition:
1. A Binary Search Tree (BST) is a binary tree with an ordering property:
→ All left child values < root < right child values.
2. No duplicate values are allowed.
3. Operations like search, insertion, and deletion are efficient (O(log n) on average).
Given Nodes:
78, 90, 45, 67, 98, 100, 23, 45, 94, 29
(Duplicate “45” ignored as BST doesn’t allow duplicates.)
Step-by-Step Construction:
Step Element Action / Position in BST
78
1 78 Root node created.
/ \
2 90 Greater than 78 → goes to right of 78.
3 45 Less than 78 → goes to left of 78. 45 90
4 67 Less than 78 but greater than 45 → right of 45. / \ \
5 98 Greater than 90 → right of 90.
23 67 98
6 100 Greater than 98 → right of 98.
\ / \
7 23 Less than 45 → left of 45.
8 94 Less than 98 but greater than 90 → left of 98. 29 94 100
9 29 Greater than 23 → right of 23.
Final BST Structure: Blue Box
Type Result
In-order 23, 29, 45, 67, 78, 90, 94, 98, 100
Pre-order 78, 45, 23, 29, 67, 90, 98, 94, 100
Post-order 29, 23, 67, 45, 94, 100, 98, 90, 78
95. Define Tree. Find Inorder, Preorder and Postorder traversals for the given
tree
Definition (short):
1. A Tree is a non-linear hierarchical data structure of nodes connected by edges.
2. It has a single root and each node may have 0 or more children.
3. Trees represent hierarchical relationships (file systems, expression trees).
4. Traversals: Inorder (L-Root-R), Preorder (Root-L-R), Postorder (L-R-Root).
Traversals:
Inorder (L Root R): 3, 12, 6, 4, 7, 10, 11, 5, 2, 8
Preorder (Root L R): 10, 12, 3, 4, 6, 7, 5, 11, 2, 8
Postorder (L R Root): 3, 6, 7, 4, 12, 11, 8, 2, 5, 10
96. What is an Expression Tree? Represent the postfix 52+31-* as an expression
tree and give equivalent infix
Definition (short):
1. An Expression Tree is a binary tree representing an arithmetic expression.
2. Internal nodes are operators; leaves are operands.
3. It helps in evaluation and conversion between infix/prefix/postfix.
Postfix: 5 2 + 3 1 - *
Build (stack method):
• push 5, push 2 → on + pop 2 & 5 → create node (+ 5 2) and push it.
• push 3, push 1 → on - pop 1 & 3 → node (- 3 1) and push it.
• on * pop (- 3 1) as right, (+ 5 2) as left → make (* (+ 5 2) (- 3 1)).
Expression Tree:
Equivalent infix (with parentheses):
(5 + 2) * (3 - 1)
97. Perform BST operations: insert [45,30,60,25,35,50,70]; delete 60; explain
successor; draw final BST
(i) Insert sequence — stepwise placement
1. Insert 45 → becomes root.
2. Insert 30 → 30 < 45 → goes left of 45. 45
3. Insert 60 → 60 > 45 → goes right of 45. / \
4. Insert 25 → 25 < 45 → go left; 25 < 30 → left of 30.
5. Insert 35 → 35 < 45 → left; 35 > 30 → right of 30. 30 60
6. Insert 50 → 50 > 45 → right; 50 < 60 → left of 60.
7. Insert 70 → 70 > 45 → right; 70 > 60 → right of 60. / \ / \
BST before deletion: 25 35 50 70
(ii) Delete node with value 60
Node 60 has two children (50 and 70). Use inorder successor (minimum in right subtree) or
predecessor. Here we use successor:
i. Right subtree of 60 is node 70 — its minimum is 70 (70 has no left child).
ii. Replace 60’s value with successor value 70, then delete the original successor
node (which is now a duplicate). Since 70 has no children, remove it directly.
(iii) Explanation of finding successor (used during deletion)
1. For a node with two children, the inorder successor is the smallest value in its right
subtree.
2. Procedure: move to node → go to its right child → then repeatedly go left until left is
NULL; that node is successor.
3. Replace the target node’s value with successor’s value, then delete successor node
(successor will have at most one child).
4. (Alternatively you can use inorder predecessor: go to left child then rightmost node.)
(iv) Final BST after deletion of 60 (after replacing by 70 and removing original 70):
(That’s the final tree: 70 replaced 60, and 50 remains left child of 70.)
45
/ \
30 70
/ \ /
25 35 50
98. Explain expression tree. Create tree for (4 + 2) * (7 - 3)
Concept (brief recap):
1. An Expression Tree is a binary tree that represents an arithmetic or logical
expression.
2. Each internal node of the tree represents an operator (+, -, *, /, ^, etc.), and each leaf
node represents an operand (number or variable).
3. The structure of the tree defines the order of operations — the operators near the root
are evaluated after those deeper in the tree (reflecting operator precedence).
4. Expression trees are used for:
o Evaluating expressions programmatically.
o Converting between infix, prefix, and postfix notations.
o Compiler design (for syntax trees and code generation).
5. Traversals on the tree give different forms of the expression:
o Inorder (L Root R): gives infix form.
o Preorder (Root L R): gives prefix form.
o Postorder (L R Root): gives postfix form.
Expression: (4 + 2) * (7 - 3)
*
Expression Tree: / \
+ -
Equivalent forms: /\ /\
• Infix (with parens): (4 + 2) * (7 - 3) 4 2 7 3
• Prefix: * + 4 2 - 7 3
• Postfix: 4 2 + 7 3 - *