Examine the following binary search tree and answer the question, nodes are valu

Question

Examine the following binary search tree and answer the question, nodes are values in the key members of the items in the tree. What is the minimum height of a binary search tree containing these nodes? What is the maximum height of a binary search tree containing these nodes? Show the order in which the nodes in the tree are processed by a postorder traversal of the tree? If a node with key value 25 is to be inserted into the tree, where would it be inserted? If node with key value 47 is to be deleted, which value could be used to replace 47? If node with key 29 is to be deleted, what replaces the pointer to node with key 29? If node with key 49 is to be deleted, what replaces the pointer to node with key 49? Show the order in which the nodes in the tree are processed by a preorder traversal of the tree.

Explanation / Answer

1)For minimal height of a 2-4 tree, we will be having three keys(maximum possible number) per node.

keys at level 0 = 3

keys at level 1 = 3*(4)

keys at level 2 = 3*(4^2) and so on . . .

Hence, height = log(n+1)(base 4) - 1

Adding total number of keys at each level we will get a GP on solving which we will get the minimal height. Solving it for a total of 10^6 keys we get:

3 * (4^0+ 4^1 + 4^2 + . .. . . . +4^h) = 10^6

(4^(h+1) - 1) = 10^6

h = log(10^6 + 1)/log(4) - 1

Minimal height of tree is 2

Binary Search Tree

For maximal height we will have a continuous chain of length n(total number of nodes) hence giving us a height equal to n-1(as height starts from 0).

For minimal height we will have a perfectly balanced tree and as solved earlier we will have a height equal to log(n+1)-1

2) For maximal height of a 2-4 tree, we will be having one key per node, hence it will behave like a Binary Search Tree.

keys at level 0 = 1

keys at level 1 = 2

keys at level 2 = 4 and so on. . . .

Adding total number of keys at each level we get a GP on solving which we will get the maximal height of the tree.

Hence, height = log(n+1)(base 2) - 1

Solving it for a total of 10^6 keys we will get :

1 * (2^0+ 2^1 + 2^2 + . .. . . . +2^h) = 10^6

1*(2^(h+1) - 1) = 10^6

h = log(10^6 + 1)/log(2) - 1

Maximal height of tree is 7

3)

Post-order traversal method:
1. Visit Left Sub-Tree
2. Visit Right Sub-Tree
3. Process Current Node

Nodes in the postorder traversal 29,22,52,49,47,69,56

4) The key value 25 is to be inserted in to the tree at left sub - tree of 29 because of 25>22 and 25<29.

5) If node with key value 47 is to be deleted, 49 value could be used to replace 47.

6) If node with key value 29 is to be deleted, then node will be deleted because it is end node there is no any sub -tree

8) Pre-order traversal method:
1. Process Current Node
2. Visit Left Sub-Tree
3. Visit Right Sub-Tree

Nodes in the preorder traversal is 56,47,22,29,47,52.69

Related Questions

Navigate

• Browse (All)
• Browse E
• Subjects

---

---

Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.