Ex$2.$ Find and Remove a Subtree

Problem Description

Write a BST member function that takes a Binary Search Tree $($BST$)$ as a parameter:

bool find$\_$remove$\_$subtree$($const BST &other$)$

The function should search for a subtree within the current BST that exactly matches the structure and values of the received BST 'other'. If a match is found, the function should delete the matching subtree from the current BST and return true. Otherwise, the function should not modify the current tree and return false.

If the entire current BST matches the received BST$,$ the function should clear the entire original BST and return true You are allowed to define and use private functions. #pragma once

#include "queue$\_$dll$.$h$"$

#include $"$dll$.$h$"$

#include

using std::string;

template

class BST;

template

class BSTNode

$\{$

public:

BSTNode$($const T& val, BSTNode$*$ left, BSTNode$*$ right$)$;

T get$\_$val$()$ const $\{$ return val; $\}$

BSTNode$*$ get$\_$left$()$ const $\{$ return left; $\}$

BSTNode$*$ get$\_$right$()$ const $\{$ return right; $\}$

private:

T val;

BSTNode$*$ left;

BSTNode$*$ right;

friend class BST;

$\}$;

template

BSTNode::BSTNode$($const T& val,

BSTNode$*$ left,

BSTNode$*$ right$)$

$\{$

this$->$val $=$ val;

this$->$left $=$ left;

this$->$right $=$ right;

$\}$

template

class BST

$\{$

public:

$//--------------------------------//$

bool find$\_$remove$\_$subtree$($const BST &other$)\{$

$//$ ADD YOUR IMPLEMENTATION HERE

$\}$

$//--------------------------------//$

BST$()$;

BST$($const BST& other$)$;

~BST$()$;

bool is$\_$empty$()$ const;

bool contains$($const T& val$)$ const;

void insert$($const T& val$)$;

bool remove$($const T& val$)$;

void clear$()$;

DLList elements$()$ const;

DLList elements$\_$level$\_$ordered$()$ const;

BSTNode$*$ get$\_$root$()$ const $\{$ return root; $\}$

BST& operator$=($const BST& other$)$;

private:

BSTNode $*$root;

void copy$\_$from$($BSTNode$*$ node$)$;

void elements$($DLList& result, BSTNode$*$ node$)$ const;

bool contains$($const T& val, BSTNode$*$ node$)$ const;

void remove$\_1($BSTNode$*$ ptr$,$ BSTNode$*$ prev$)$;

void remove$\_2($BSTNode$*$ node$)$;

void clear$($BSTNode$*$ node$)$;

$\}$;

template

BST::BST$()$

$\{$

root $=$ nullptr;

$\}$

template

void BST::copy$\_$from$($BSTNode$*$ node$)\{$

if $($node $==$ nullptr$)$

return;

insert$($node$->$val$)$;

copy$\_$from$($node$->$left$)$;

copy$\_$from$($node$->$right$)$;

$\}$

template

BST::BST$($const BST& other$)\{$

root $=$ nullptr;

copy$\_$from$($other$.$root$)$;

$\}$

template

BST::~BST$()$

$\{$

clear$()$;

$\}$

template

bool BST::is$\_$empty$()$ const

$\{$

return root $==$ nullptr;

$\}$

$//$ Iterative implementation of searching in the tree.

template

bool BST::contains$($const T& val$)$ const

$\{$

BSTNode$*$ node $=$ root; $//$ always start the search from the root

while$($node $!=$ nullptr$)\{$

$//$ If the current node has the value we are looking for

if $($val $==$ node$->$val$)$

return true;

$//$ If the value that we are looking for is smaller than the

$//$ value of the current tree node, go left; else, go right

if$($val $<$ node$->$val$)$

node $=$ node$->$left;

else

node $=$ node$->$right;

$\}$

$//$ If the loop completes, node is necessarily a null pointer,

$//$ which means that val was not found in the tree

return false;

$\}$

$//$ inserts the given val into the tree if it is not already in the tree.

template

void BST::insert$($const T& val$)$

$\{$

$//$ if the tree is empty, the root needs to point at the new node.

if $($is$\_$empty$())\{$

root $=$ new BSTNode$($val$,$ nullptr, nullptr$)$;

return;

$\}$

BSTNode$*$ curr $=$ root;

BSTNode$*$ prev $=$ nullptr;

$//$ Loop to search for the right position for val

while$($curr $!=$ nullptr$)\{$

prev $=$ curr;

if $($val $<$ curr$->$val$)$

curr $=$ curr$->$left;

else if $($val $>$ curr$->$val$)$

curr $=$ curr$->$right;

else

return;

$\}$

BSTNode$*$ new$\_$node $=$ new BSTNode$($val$,$ nullptr, nullptr$)$;

if $($val $<$ prev$->$val$)$

prev$->$left $=$ new$\_$node;

else

prev$->$right $=$ new$\_$node;

$\}$

$//$ Breadth$-$first traversal

template

DLList BST::elements$\_$level$\_$ordered$()$ const

$\{$

DLList result;

if $($root $==$ nullptr$)$

return result;

$//$ a queue of pointers to BSTNode objects.

QueueDLL$*>$ queue;

BSTNode$*$ node $=$ root;

queue.enqueue$($node$)$;

while $(!$queue.is$\_$empty$())\{$

$//$ Take a node out of the queue, process it and then insert

$//$ its children into the queue.

node $=$ queue.dequeue$()$;