Trees

This chapter introduces the tree data structure, a hierarchical data structure. It covers tree terminology, types of trees (binary, AVL, B-tree), and tree traversals. The chapter also explains tree operations like insertion, deletion, and searching.

Question and Solution.

2079 Ashwin

Construct a recursion tree for Tower of Hanoi (for) with 'n' disks. Construct a recursion tree and show all the sequence of movements for 4 disks.

Solution A recursion tree is a visual representation of the recursive calls made during the execution of an algorithm. The Tower of Hanoi is a classic puzzle involving three rods and a set of disks of varying sizes. The objective is to move all the disks from one rod (source) to another (destination) using a third rod (auxiliary) while adhering to the following rules:

Only one disk can be moved at a time.
A larger disk cannot be placed on top of a smaller disk.

Here's the recursion tree for 4 disks:

Sequence movement of disk:

1.Move disk 1 from A to B.
2.Move disk 2 from A to C.
3.Move disk 1 from B to C.
4.Move disk 3 from A to B.
5.Move disk 1 from C to A.
6.Move disk 2 from C to B.   
7.Move disk 1 from A to B.   
8.Move disk 4 from A to C.
9.Move disk 1 from B to C.
10.Move disk 2 from B to A.
11.Move disk 1 from C to A.
12.Move disk 3 from B to C.
13.Move disk 1 from A to B.
14.Move disk 2 from A to C.
15.Move disk 1 from B to C.

2078 Ashwin

Construct an AVL tree for the following data: 10, 20, 30, 40, 50, 25, 15. Show the tree after each insertion and the type of rotation used.

Solution To construct an AVL tree by inserting the elements 10, 20, 30, 40, 50, 25, 15. in the given order, along with visual representations of the tree at each stage:
To be a AVL tree it must satisfy the come condition:

Tree must be a binary search tree (BST).
( Height of left subtree - height of right subtree ) should be the subset of {-1,0,1}.

2078 Ashwin (Back)

Construct a B-tree of order 3 for the given set of keys: 2, 5, 10, 12, 18, 20, 22, 25, 30, 35, 40. Show the tree after each insertion.

Solution A B-tree is a self-balancing tree where all the leaf nodes are at the same level which allows for efficient searching, insertion and deletion of records.
To construct a B-tree of order 3 of the data: 2, 5, 10, 12, 18, 20, 22, 25, 30, 35, 40. The data are stored in ascending order & it contains:

Maximum child = 3
Maximum keys = 3-1 = 2

2078 Chaitra (Back)

Explain how a height balanced tree is different from an unbalanced tree? Explain the applications of height balanced tree.

Solution A height-balanced tree ensures that the difference in height between the left and right subtrees of any node is at most one. This keeps the tree roughly balanced, ensuring operations like search, insert, and delete are efficient (O(log n)).

An unbalanced tree has no such constraint, which can lead to skewed structures (e.g., a linked list in the worst case), resulting in degraded performance for these operations (O(n)).

Expample

Application of height balanced tree.

Height-balanced trees have various applications where efficient data storage and retrieval are required. Some common applications include:

1.Databases: Used in database indexing (e.g., AVL trees, Red-Black trees) to ensure fast query processing.

2.File Systems: For maintaining directory structures, allowing quick access to files and subdirectories.

3.Symbol Tables: Used in compilers for efficient storage and lookup of identifiers.

4.Routing Tables: In networking, for efficient storage and retrieval of routing information.

5.Search Engines: To maintain balanced indices for faster keyword search and retrieval.

2078 Chaitra

Explain pre-order and in-order tree traversal with example. Construct an AVL-balanced tree with given set of data: 15,20,24,10,13,7,30,16,25

Solution

Preorder: A preorder traversal is a type of tree traversal that visits the root node first, followed by the left subtree, and then the right subtree. It is called a preorder traversal because the root node is always visited before any of its child nodes.The rules is:

Visit the root node of the subtree.(Node/Root)
Then left subtree is traversed (Left).
At last, right subtree is traversed (Right).

Algorithm for the preorder traversal.
Preorder(root):
1.If root is NULL then return
2.Process root (For example, print root’s data)
3.Preorder (root -> left)
4.Preorder (root -> right)

example

Inorder: Inorder traversal is defined as a type of tree traversal technique which follows the Left-Root-Right pattern, such that:

The left subtree is traversed first.(Left)
2.Then the root node for that subtree is traversed.(Root/Node)
Finally, the right subtree is traversed.(Right)

Algorithm for the inorder traversal.
inorder(root):
1.If root is NULL then return
2.Inorder (root -> left).
3.Process root (For example, print root’s data)
4.Inorder (root -> right)

example

To construct an AVL tree by inserting the elements 15,20,24,10,13,7,30,16,25 in the given order, along with visual representations of the tree at each stage:
To be a AVL tree it must satisfy the come condition:

Tree must be a binary search tree (BST).
( Height of left subtree - height of right subtree ) should be the subset of {-1,0,1}.

2078 Baisakh

Define red-black tree with example. Construct an AVL tree by inserting following elements in given order: 53,9,19,2,7,13,1,48,99,81,41.

SolutionA Red-Black Tree is a self-balancing binary search tree where each node has an additional attribute: a color, which can be either red or black.

Example

To construct an AVL tree by inserting the elements 53, 9, 19, 2, 7, 13, 1, 48, 99, 81, 41 in the given order, along with visual representations of the tree at each stage:
To be a AVL tree it must satisfy the come condition:

Tree must be a binary search tree (BST).
( Height of left subtree - height of right subtree ) should be the subset of {-1,0,1}.

2075 Bhadra

Define almost complete binary tree. Construct a tree from its given preorder and inorder traversals.
Inorder:EACKFHDBG
Preorder:FAEKCDHGB

Solution It is a tree where nodes are completely filled up to the second last level, and the last level is filled from left to right without gaps.

Almost Complete Binary Tree Visualization

Construction of Tree from Preorder and Inorder Traversal

2074 Bhadra

Discuss about AVL rotations with suitable examples. Create a AVL balanced tree for data sequence 10 20 30 50 45 40 8 5 3.

Solution If the difference in the height of left and right sub-trees is more than 1 or less than -1 then the tree is unbalanced and we need to make height balance by using some rotation techniques as:
1.Left rotation: If a tree becomes unbalanced, when a node is inserted into the right subtree then we perform single left rotation as below:

example

2.Right rotation: If a tree becomes unbalanced , when a node is inserted into left subtree then we perform single, right rotation as below: example

Left-right rotation: If a tree becomes unbalanced, when a node is inserted into the right of left subtree, then we use double rotation: first we perform left rotation then we perform right rotation. example

Right-left rotation: If a tree becomes unbalanced when a node is inserted into the left of right sub-tree then we use double rotation: first we perform right rotation then we perform left rotation as below: example

To construct an AVL tree by inserting the elements 10 20 30 50 45 40 8 5 3. in the given order, along with visual representations of the tree at each stage:
To be a AVL tree it must satisfy the come condition: