17. [3] Suppose we have a binary search tree and while performing a traversal, w

Question

17. [3] Suppose we have a binary search tree and while performing a traversal, we insert the objects into a new binary search tree as we visit each node. Which of the four traversals (breadth-first; and pre-, in-, and post-order depth- first traversals) will produce the identical binary search tree (same root, children, etc.)? 18. [7] Implement a function remove_front which removes the least object in a binary search tree. You may assume that the BST_node class has two relevant member variables left_tree and right_tree. Remember to delete this.

Explanation / Answer

17) Breadth first traversal and pre-order traversal will produce an identical BST.

18)

template <typename Object>

void BST_node<Object>::remove_front( BST_node *ptr_to_this){

if(ptr_to_this->left_tree==NULL)
    ptr_to_this=ptr_to_this->right_tree;
else
{
    BST_node *tr=ptr_to_this;
    while(tr->left_tree->left_tree!=NULL)
    {
        tr=tr->left_tree;
    }
    if(tr->left_tree->right_tree==NULL)
    {
        tr->left_tree==NULL;
    }
    else
    {
        tr->left_tree=tr->left_tree->right_tree;
    }
}

}

In case left_tree and right_tree variables are private you would beed to replace all references to left_tree and right_tree by the get_left_tree() and get_right_tree() respectively.

Related Questions

Navigate

• Browse (All)
• Browse 1
• Subjects

---

---

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