Assume this tree is a binary search tree even though you cannot see what the key

Question

Assume this tree is a binary search tree even though you cannot see what the keys and values are at the nodes (the letters we write below are just "names" for the nodes for the purpose of answering the questions). (a) What node is the successor of node A? (b) What node is the successor of node B? (c) What node is the successor of node C? (d) What is the height of the tree? (e) What is the maximum number of nodes that could be added to the tree without increasing its height? (f) Is the tree an AVL tree? (g) If we remove only node H, is the result an AVL tree? (h) If we remove only node J, is the result an AVL tree? (i) If we remove only node K, is the result an AVL tree?

Explanation / Answer

a) We find the successor node by performing the following steps:

THE SUCCEESSOR OF NODE A IS J

b)    THE SUCCEESSOR OF NODE B IS E

c)   THE SUCCEESSOR OF NODE C IS K

d) hl = height( left subtree of t);

hr = height( right subtree of t);

h = 1 + maximum of hl and hr;

FOR THE GIVEN TREE hl=3 AND hr=4 AND THEREFORE HEIGHT h=5

e) MAXIMUM OF 10 nodes CAN BE ADDED WITHOUT INCREASING THE HEIGHT 18

f) YES THE ABOVE BST IS AN AVL TREE BECAUSE   the difference between heights of left and right subtrees is not more than one for all nodes.

g) NO THE RESULT IS NOT AN AVL TREE BECAUSE NODE A VIOLATES THE AVL PROPERTY

h) NO THE RESULT IS NOT AN AVL TREE BECAUSE NODE C VIOLATES THE AVL PROPERTY

i) NO THE RESULT IS NOT AN AVL TREE BECAUSE NODE G VIOLATES THE AVL PROPERTY

Related Questions

Navigate

• Browse (All)
• Browse A
• Subjects

---