BCA Semester 3 – Data Structure and Algorithms – Unit 7: Trees (5Hrs)

Draw a BST from the string DATASTRUCTURE and traverse the tree in post order and preorder.

Define AVL tree. Construct AVL tree from given data set:$4, 6, 12, 9, 5, 2, 13, 8, 3, 7, 11.$

What do you mean by Huffman Algorithm? Explain with example. Construct the B tree of order 5 using following data: $20, 10, 26, 55, 80, 11, 9, 60, 67, 55, 22, 76, 56, 45, 34, 100, 150$

Differentiate between BST and AVL tree. Given the following AVL Tree:

1digraph Tree {
2    node [shape=circle];
3    5 -> 3;
4    5 -> 10;
5    3 -> 2;
6    3 -> 4;
7    2 -> 1;
8    10 -> 7;
9    10 -> 11;
10    7 -> 6;
11    7 -> 9;
12    9 -> 8;
13    11 -> 12;
14}

Draw the resulting BST after 5 is removed, but before any rebalancing takes place. Label each node in the resulting tree with its balance factor. Replace a node with both children using an appropriate value from the node's left child.

What are the depth and degree of a node in a tree? Perform pre-order, in-order and post- order traversal of the following tree:

1digraph Tree {
2    node [shape=circle];
3    G -> K;
4    G -> H;
5    K -> D;
6    K -> M;
7    M -> C;
8    M -> E;
9    H -> A;
10    H -> B;
11    A -> F;
12    A -> N;
13}

What is an AVL tree? Create an AVL tree from the following data: $18, 12, 14, 8, 5, 25, 31, 24, 27$

What is B-tree? How insertions and deletions of elements can be done in a B-tree.