Let T be a binary search tree. Suppose we want to include a field v.size, the nu
ID: 3799458 • Letter: L
Question
Let T be a binary search tree. Suppose we want to include a field v.size, the number of items stored in the subtree of v, at each node v.
a. Given T, describe an algorithm that will populate all the size fields in T. What is the running time of your algorithm?
b. Now suppose we make modifications to T by inserting or removing items. For each modification – i.e., an insertion or a removal – describe the modifications that have to be made to the size fields of the nodes in T. How much time will such modifications take?
Explanation / Answer
a) Algorithm:
visit each node of the binary search tree using DFS
When we visit node v of the binary search tree in DFS, we calculate number of items stored in the subtree of v, at each node v by calling DFS as v.
And in this way we can populate all the size fields in T.
As the time complexity of DFS is O(V+E),The time complexity of our algorithm will be O( [V+E]*[V+E] ) , where V is number of nodes in BST, and E is number of edges.
b) Algorithm:
1) Insertion: When we add an element v into BST, we need to increase the size fields of the ancestors of v by 1.
2) Deletion: When we remove an element v from BST, we need to decrease the size fields of the ancestors of v by 1.
We can find all the ancestors of a node v in O(n) time where n is number of nodes in the BST.
Psuedocode to find all the ancestors of a node v in O(n) time:
printAncestors(root,target)
{
if (root == NULL)
return false; // Base case
if (root == target)
return true;
if ( printAncestors(root->left, target) || printAncestors(root->right, target) )
{
cout << root->data << " "; // if target is descendent of root, print root
return true;
}
}
Related Questions
Navigate
Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.