Data Structures & Algorithms

Unit-3 Trees
Two Marks

1. Define Binary Tree

A Binary Tree is a hierarchical data structure in which each node has
at most two children, referred to as the left child and the right child.
A
/\
B C
/\
D E
___________________________________________________________________
2. Differentiate between B-Tree and B+ Tree

Feature B-Tree B+ Tree

Both internal and leaf Only leaf nodes store data

Data
nodes store keys and pointers; internal nodes
Storage
data pointers. store only keys for indexing.

All leaf nodes are linked

Leaf nodes are not together in a linked list,
Leaf Nodes
linked together. enabling efficient range
queries.

Number of A node with m keys A node with m keys has

Children has m+1 children. exactly m children.
Feature B-Tree B+ Tree

Faster for range queries and

Search Slower for range queries
sequential access due to
Efficiency as data is scattered.
linked leaf nodes.

___________________________________________________________________
3.Define Binary Search Tree
A Binary Search Tree (BST) is a binary tree with a special ordering property:
for any node, the values in its left subtree are all less than the node's value,
and the values in its right subtree are all greater than the node's value.
5
/\
2 8
/\
1 3
___________________________________________________________________
4. What is AVL Tree?
An AVL Tree is a self-balancing Binary Search Tree where the difference
between the heights of the left and right subtrees (the balance factor) for
any node is at most 1. This balancing ensures operations like search,
insertion, and deletion remain efficient (O(log n)).
___________________________________________________________________
5. List out the applications of trees.
• Hierarchical Data: Representing file systems, organizational charts,
and XML/HTML DOM.
• Efficient Searching: Binary Search Trees enable fast lookup,
insertion, and deletion.
• Heap Data Structure: Used for efficient priority queues and heap
sort.
 • Routing Algorithms: Trie trees are used in networking for IP routing
tables.
___________________________________________________________________
6. What is a complete binary tree? Give an example with diagram.
A complete binary tree is a binary tree in which every level, except possibly
the last, is completely filled, and all nodes in the last level are as far left as
possible.
Example:
text
1
/\
2 3
/\
4 5
This tree has three levels. The last level (containing 4 and 5) is not full, but
its nodes are positioned to the left, making it complete.
___________________________________________________________________
7. Differentiate complete and full binary tree

Feature Full Binary Tree Complete Binary Tree

Every node has All levels are completely filled

Definition either 0 or 2 except possibly the last, which must
children. be filled from left to right.

Node No specific The number of nodes n is

Count relationship between 2^(h) and 2^(h+1)-1.
between height
Feature Full Binary Tree Complete Binary Tree

and number of
nodes.

A tree where no
A heap is typically a complete
Example node has only one
binary tree.
child.

___________________________________________________________________
8. Find the Inorder tree traversal for this tree.
• Inorder Traversal Formula: Left Subtree -> Root -> Right Subtree
• Final Answer: 10, 20, 30, 100, 150, 200, 300
___________________________________________________________________
9. Define balance factor in AVL tree.
The balance factor of a node in an AVL tree is an integer value calculated as
the difference between the height of its left subtree and the height of its
right subtree.
Formula: Balance Factor = (Height of left subtree) - (Height of right subtree)
___________________________________________________________________
10. Where is the minimum element found in a Min-Heap?
In a Min-Heap, the minimum element is always found at the root node. This
is a direct consequence of the heap property, which mandates that any
node's value must be less than or equal to the values of its children (for a
Min-Heap). Since this rule applies to every single node in the tree, the
smallest value in the entire structure must propagate to the very top, the
root.
___________________________________________________________________
11. Define tree traversal and mention the types of traversals
Tree traversal is the process of visiting each node in a tree data structure
exactly once in a specific order.
The three main types of traversals for binary trees are:
1. Inorder: Left subtree, Root, Right subtree.
2. Preorder: Root, Left subtree, Right subtree.
3. Postorder: Left subtree, Right subtree, Root.
___________________________________________________________________
12. What is the degree of a node in a tree?
The degree of a node in a tree is defined as the number of direct children
(immediate descendants) that node possesses.
• In a general tree (not necessarily binary), a node can have a degree of
any non-negative integer.

Ten Marks

1. Explain the different types of tree traversals with suitable examples.

(C03 L2)
Tree traversal refers to the process of visiting each node in a tree data
structure exactly once in a systematic manner. Different traversal methods
visit nodes in different orders, serving different purposes. In binary trees,
there are three fundamental traversal techniques:
1. Inorder Traversal (Left, Root, Right)
• Algorithm:
1. Recursively traverse the left subtree.
2. Visit the root node.
3. Recursively traverse the right subtree.
 • Characteristics: For Binary Search Trees (BSTs), this traversal yields
nodes in ascending sorted order. It's commonly used when sorted
output is needed.
• Example: Consider the tree:
text
A
/\
B C
/\
D E
Inorder traversal: D, B, E, A, C
• Process:
1. Start at A, go to left subtree B
2. At B, go to left subtree D (D has no children, so visit D)
3. Return to B and visit B
4. Go to right subtree E (visit E)
5. Return to A and visit A
6. Go to right subtree C (visit C)
2. Preorder Traversal (Root, Left, Right)
• Algorithm:
1. Visit the root node.
2. Recursively traverse the left subtree.
3. Recursively traverse the right subtree.
• Characteristics: This traversal is used to create a copy of the tree or
to get prefix expressions from expression trees.
• Example: Using the same tree:
text
A
/\
B C
/\
D E
Preorder traversal: A, B, D, E, C
• Process:
1. Visit A first
2. Then go to left subtree B (visit B)
3. From B, go to left subtree D (visit D)
4. Return to B, then go to right subtree E (visit E)
5. Return to A, then go to right subtree C (visit C)
3. Postorder Traversal (Left, Right, Root)
• Algorithm:
1. Recursively traverse the left subtree.
2. Recursively traverse the right subtree.
3. Visit the root node.
• Characteristics: This traversal is used to delete the tree or to get
postfix expressions from expression trees.
• Example: Using the same tree:
text
A
/\
B C
/\
D E
Postorder traversal: D, E, B, C, A
• Process:
1. Start at A, go to left subtree B
2. At B, go to left subtree D (visit D)
3. Return to B, go to right subtree E (visit E)
4. Visit B
5. Return to A, go to right subtree C (visit C)
6. Finally visit A
These traversal methods form the basis for many tree operations and
algorithms, each serving specific purposes in tree manipulation and data
processing.
2. BST Traversals (C03 L3)
a) Constructed BST from {15, 10, 20, 8, 12, 17, 25}:
text
15
/ \
10 20
/\ /\
8 12 17 25
Traversals:
• Inorder (Left, Root, Right): 8, 10, 12, 15, 17, 20, 25
• Preorder (Root, Left, Right): 15, 10, 8, 12, 20, 17, 25
• Postorder (Left, Right, Root): 8, 12, 10, 17, 25, 20, 15
b) Verification: The Inorder traversal (8, 10, 12, 15, 17, 20, 25) gives the
elements in sorted order. This is a fundamental property of a Binary Search
Tree.
3. Expression Tree (C03 L3)
An expression tree is a binary tree used to represent arithmetic
expressions. In it:
• Leaf nodes are operands (e.g., A, B, 5, 10)
• Internal nodes are operators (e.g., +, -, *, /)
Construction for (A + B) * (C - D):
The expression is built from the bottom up. The operator * is the root. Its left
subtree is the expression (A + B) and its right subtree is (C - D).
text
*
/\
+ -
/\/\
A BC D
Evaluation:
The tree is evaluated recursively (often using a postorder traversal):
1. Evaluate the left subtree (A + B), result = L
2. Evaluate the right subtree (C - D), result = R
3. Apply the operator at the root * to the results: L * R
4. Insertion and Deletion in a BST (C03 L3)
Insertion Operation: To insert a new key k into a BST:
1. Start at the root
2. Compare k with the current node
3. If k is less, go to the left child; if greater, go to the right child
 4. Repeat step 3 until you reach a NULL pointer
5. Insert k at this NULL position
Constructing the BST:
• Insert 50: 50 (Root)
• Insert 30: 50 / 30
• Insert 20: 50 / 30 / 20
• Insert 40: 50 / 30 / \ 20 40
• Insert 70: 50 / \ 30 70 / \ 20 40
• Insert 60: 50 / \ 30 70 / \ / 20 40 60
• Insert 80: 50 / \ 30 70 / \ / \ 20 40 60 80 (Final Tree)
Deletion of node 40:
Node 40 is a leaf node (it has no children). Deletion is straightforward:
simply remove the node from the tree.
Tree after deletion:
text
50
/ \
30 70
/ / \
20 60 80
5. Priority Queue and Heap (C03 L2)
• Priority Queue: An abstract data type where each element has a
"priority". Elements are served based on highest priority (Max-Heap)
or lowest priority (Min-Heap), not in FIFO order.
• Heap: A complete binary tree that is commonly used to efficiently
implement a priority queue. It satisfies the heap property:
 o Max-Heap: The value of any node is greater than or equal to the
values of its children. The largest element is at the root.
o Min-Heap: The value of any node is less than or equal to the
values of its children. The smallest element is at the root.
Example (Max-Heap Insertion):
Insert: 10, 30, 20, 5, 40
1. Insert 10: [10]
2. Insert 30: [10, 30] → Violates heap property. Swap with parent → [30,
10]
3. Insert 20: [30, 10, 20] → Valid Max-Heap
4. Insert 5: [30, 10, 20, 5] → Valid Max-Heap
5. Insert 40: [30, 10, 20, 5, 40] → 40 > its parent (10). Swap → [30, 40, 20,
5, 10] → 40 > its new parent (30). Swap → [40, 30, 20, 5, 10] (Final Max-
Heap)
Tree representation:
text
40
/ \
30 20
/\
5 10
6. AVL Tree Insertion (C03 L3)
An AVL tree requires the balance factor (height(left) - height(right)) of every
node to be -1, 0, or 1. Rotations are performed to maintain this.
Insertion Sequence: 10, 20, 30, 40, 50, 25
1. Insert 10: 10 (Balance Factor: 0)
2. Insert 20: 10 \ 20 → BF(10) = -2. Left Rotation on 10 → 20 / 10
 3. Insert 30: 20 / \ 10 30 → Balanced
4. Insert 40: 20 / \ 10 30 \ 40 → BF(30) = -1, BF(20) = -2. Left Rotation on
20 → 30 / \ 20 40 / 10
5. Insert 50: 30 / \ 20 40 / \ 10 50 → BF(40) = -1, BF(30) = -2. Left Rotation
on 30 → 40 / \ 30 50 / 20 / 10 → Now BF(30) = +2. This is a Left-Right
Case. Requires a Right Rotation on 20 first, then a Left Rotation on 30
→ Correct Final Tree: 40 / \ 20 50 / \ 10 30
6. Insert 25: 40 / \ 20 50 / \ 10 30 → Insert 25 as right child of 20: 20 / \ 10
30 / 25 → Check Balance: BF(30) = +1 (ok), BF(20) = -1 (ok), BF(40) =
|(2)-(1)| = 1 (ok). The tree is balanced.
Final AVL Tree:
text
40
/ \
20 50
/ \
10 30
/
25
7. B+ Tree of Order 4 (C03 L3)
Order m=4 means max keys per node is 3 (m-1), and min is ceil(m/2)-1 = 1.
Max pointers/children is 4.
Insertion Sequence: 5, 15, 25, 35, 45, 55, 65, 75
1. Insert 5, 15, 25: [5, 15, 25] (Leaf Node)
2. Insert 35: Splits the leaf. [5, 15] and [25, 35]. Promote middle value
25 to root → Internal: [25], Leaves: [5,15] → [25,35]
3. Insert 45: Insert into [25,35] → [25,35,45]
 4. Insert 55: Insert into [25,35,45] → Splits. New
leaves: [25,35] and [45,55]. Promote 45 to root. Root is now [25,45] →
Internal: [25,45], Leaves: [5,15] → [25,35] → [45,55]
5. Insert 65: Insert into [45,55] → [45,55,65]
6. Insert 75: Insert into [45,55,65] → Splits. New
leaves: [45,55] and [65,75]. Promote 65 to root. Root [25,45,65] is full
→ Internal: [25,45,65], Leaves: [5,15] → [25,35] → [45,55] → [65,75]
Leaf Node Linking: The leaf nodes are linked in a sequential linked list, as
shown by the arrows (→). This allows efficient range queries.
8. B-Tree of Order 3 (C03 L3)
Order m=3 means max keys per node is 2 (m-1), and min is ceil(m/2)-1 = 1.
Max children is 3.
Insertion Sequence: 10, 20, 5, 6, 12, 30, 7, 17
1. Insert 10: [10]
2. Insert 20: [10,20]
3. Insert 5: [5,10,20] → Node overflow. Split. Promote middle 10. New
root → [10] with children [5] and [20]
4. Insert 6: Insert into leaf [5] → [5,6]
5. Insert 12: Insert into leaf [20] → [12,20]
6. Insert 30: Insert into leaf [12,20] → [12,20,30] → Overflow. Split leaf.
Promote middle 20 to root → Root [10,20], Children [5,6], [12], [30]
7. Insert 7: Insert into leaf [5,6] → [5,6,7] → Overflow. Split leaf. Promote
middle 6 to root → Root [6,10,20] → Root overflow. Split root. Promote
middle 10 → New Root [10], Left Child [6] (with children [5] and [7]),
Right Child [20] (with children [12] and [30])
8. Insert 17: Insert into [12] → [12,17]
Tree after insertions:
text
 [10]
/ \
[6] [20]
/\ / \
[5] [7] [12,17] [30]
Deletion of node 6:
1. Find node containing 6. It is in the internal node [6]
2. Since 6 is an internal node, we find its inorder predecessor (largest
value in left subtree) which is 5, or its inorder successor (smallest
value in right subtree) which is 7. We choose the successor 7
3. Replace 6 with 7 in the internal node. The node becomes [7]
4. Now we must delete 7 from the leaf node [7]. Deleting it makes the
leaf empty
5. Handle underflow: merge with left sibling [5] and bring down parent
key 7 → new leaf [5,7]
6. Now the internal node [7] is empty → underflow
7. Merge empty node with parent key 10 and sibling [20] → new
node [10,20] with children [5,7], [12,17], [30]
8. Root becomes [10,20]
Final B-Tree after deletion:
text
[10,20]
/ | \
[5,7] [12,17] [30]