If an item is to be inserted into the tree whose key data member is less than th
ID: 3846408 • Letter: I
Question
If an item is to be inserted into the tree whose key data member is less than the key data member is node 1 but greater than the key data member in node 5, where would it be inserted? (b). If node 1 is to be deleted, the value in which nodes could be used to replaced it? (c). 4 2 7 5 1 6 8 3 is a traversal of the tree in which order? (d). 1 2457368 is a traversal of the tree in which order? Which tree traversal corresponds to a depth first graph traversal? Which tree traversal corresponds to a breadth first graph traversal? What auxiliary structure is used for a breadth-first traversal of a graph? What auxiliary structure is used for a depth-first traversal of a graph? What do binary search trees and heaps have in common? What makes them different?Explanation / Answer
(a)if the value is greater than the data of node 5 and less than the data of node 1 then it will be inserted as the right child of node 5 .And the traversal of type inorder after that value would be 4 ,2 ,7 ,5 , value_to_insert ,1 ,6 ,8 ,3 .
(b)This is a complex case . so we can replace the root node1 with the node of minimum value .let's suppose given nodes are also the representatives of their data too then node1 can be replaced by node 3 because here the value 3 is minimum among the elements of right tree.
So as an approach we can do this -
->find a minimum value in the right subtree
->replace value of the node to be removed with found minimum .Now,right subtree contains a duplicate !
-> apply remove to right subtree to remove a duplicate.
(c) the order of traversal is inorder traversal
->traverse the left subtree in inorder
->visit the root
->traverse the right subtree in inorder
so traversing 4 2 7 5 1 6 8 3 is inorder traversal.
(d) the order of traversal is preorder traversing
-> visit the root
->traverse the left subtree in preorder
->traverse the right subtree in preoder
so the visit of the nodes in order 1 2 4 5 7 3 6 8 is the preorder of traversal .