#include

#include "bintree.h$"$

#include $//$input and output

$//$ Constructors

BinTree::BinTree$()$ : root$($nullptr$)\{\}$

$//$ Copy constructor

BinTree::BinTree$($const BinTree &other$)$ : root$($copyTree$($other$.$root$))\{\}$

$//$ Assignment operator

BinTree &BinTree::operator$=($const BinTree &other$)\{$

if $($this $!=$ &other$)\{$

clearTree$($root$)$;

root $=$ copyTree$($other$.$root$)$;

$\}$

return $*$this;

$\}$

$//$ Destructor

BinTree::~BinTree$()\{$

clearTree$($root$)$;

$\}$

$//$ isEmpty$()$

bool BinTree::isEmpty$()$ const $\{$

return root $==$ nullptr;

$\}$

bool BinTree::retrieve$($const string &target, Node $*$&retrieved$)$ const $\{$

return retrieveHelper$($root$,$ target, retrieved$)$;

$\}$

bool BinTree::retrieveHelper$($Node $*$root$,$ const string &target, Node $*$&retrieved$)$ const $\{$

if $($root $==$ nullptr$)\{$

retrieved $=$ nullptr;

return false;

$\}$

if $($root$->$data $==$ target$)\{$

retrieved $=$ root;

return true;

$\}$ else if $($root$->$data $<$ target$)\{$

return retrieveHelper$($root$->$right, target, retrieved$)$;

$\}$ else if $($root$->$data $>$ target$)\{$

return retrieveHelper$($root$->$left, target, retrieved$)$;

$\}$

retrieved $=$ nullptr;

return false;

$\}$

bool BinTree::insert$($const string &inserting$)\{$

return insertHelper$($root$,$ inserting$)$;

$\}$

bool BinTree::insertHelper$($Node $*$&root, const string &inserting$)\{$

if $($root $==$ nullptr$)\{$

root $=$ new Node;

root$->$data $=$ inserting;

root$->$left $=$ nullptr;

root$->$right $=$ nullptr;

return true;

$\}$ else if $($inserting $<$ root$->$data$)\{$

return insertHelper$($root$->$left, inserting$)$;

$\}$ else if $($inserting $>$ root$->$data$)\{$

return insertHelper$($root$->$right, inserting$)$;

$\}$ else $\{$

$//$ Duplicate values are not allowed

return false;

$\}$

$\}$

$//$ displayTree$()$

void BinTree::displayTree$()$ const $\{$

displayTreeHelper$($root$,$ cout, $"")$;

$\}$

$//$ displayTreeHelper$()$

void BinTree::displayTreeHelper$($const Node $*$root$,$ ostream &os$,$ const string &prefix$)$ const $\{$

if $($root $!=$ nullptr$)\{$

os $<<$ prefix $<<$ root$->$data $<<$ endl;

$//$ Explicitly cast prefix to a non$-$const string before modifying

string mutablePrefix $=$ const$\_$cast$($prefix$)$;

displayTreeHelper$($root$->$left, os$,$ mutablePrefix $+"$L$--")$;

displayTreeHelper$($root$->$right, os$,$ mutablePrefix $+"$R$--")$;

$\}$

$\}$

$//$ displaySideways$()$

void BinTree::displaySideways$()$ const $\{$

displaySidewaysHelper$($root$,0)$;

$\}$

void BinTree::displaySidewaysHelper$($const Node $*$node$,$ int level$)$ const $\{$

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

displaySidewaysHelper$($node$->$right, level $+1)$;

for $($int i $=0$; i $<$ level; i$++)\{$

cout $<<""$;

$\}$

cout $<<$ node$->$data $<<$ endl;

displaySidewaysHelper$($node$->$left, level $+1)$;

$\}$

$\}$

$//$ getHeight$()$

int BinTree::getHeight$($const string &target$)$ const $\{$

return getHeightHelper$($root$,$ target$)$;

$\}$

$//$ Overloaded operators

bool BinTree::operator$==($const BinTree &other$)$ const $\{$

return compareTrees$($root$,$ other.root$)$;

$\}$

bool BinTree::operator!$=($const BinTree &other$)$ const $\{$

return $!(*$this $==$ other$)$;

$\}$

void BinTree::bstreeToArray$($string arr$[])\{$

int index $=0$;

bstreeToArrayHelper$($root$,$ arr, index$)$;

makeEmpty$()$; $//$ make the tree empty after converting to array

$\}$

void BinTree::bstreeToArrayHelper$($Node $*$root$,$ string arr$[],$ int &index$)\{$

if $($root $!=$ nullptr$)\{$

bstreeToArrayHelper$($root$->$left, arr, index$)$;

arr$[$index$++]=$ root$->$data;

bstreeToArrayHelper$($root$->$right, arr, index$)$;

delete root; $//$ deallocate the node after storing data in the array

$\}$

$\}$

void BinTree::arrayToBSTree$($string arr$[])\{$

makeEmpty$()$;

int high $=0$;

int index $=0$;

while $($index $<$ ARRAYSIZE$)\{$

if $(!$arr$[$index$].$empty$())\{$

high$++$;

$\}$ else $\{$

arr$[$index$]=""$; $//$ Set empty string

$\}$

index$++$;

$\}$

arrayToBSTreeHelper$($root$,$ arr, $0,$ high $-1)$;

$\}$

void BinTree::arrayToBSTreeHelper$($Node $*$&root, string arr$[],$ int low, int high$)\{$

if $($low $<=$ high$)\{$

int mid $=($low $+$ high$)/2$;

string temp $=$ arr$[$mid$]$;

arr$[$mid$]=""$;

if $($root $==$ nullptr$)\{$

root $=$ new Node;

root$->$data $=$ temp;

root$->$left $=$ nullptr;

root$->$right $=$ nullptr;

$\}$

$//$ Corrected recursive calls

arrayToBSTreeHelper$($root$->$left, arr, low, mid $-1)$;

arrayToBSTreeHelper$($root$->$

right, arr, mid $+1,$ high$)$;

$\}$

$\}$

void BinTree::clearTree$($Node $*$&node$)\{$

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

clearTree$($node$->$left$)$;

clearTree$($node$->$right$)$;

delete node;

node $=$ nullptr;

$\}$

$\}$

Node$*$ BinTree::copyTree$($const Node$*$ sourceNode$)\{$

if $($sourceNode $==$ nullptr$)\{$

return nullptr;

$\}$ else $\{$

Node$*$ newNode $=$ new Node$(*$sourceNode$)$; $//$ Copy data

newNode$->$left $=$ copyTree$($sourceNode$->$left$)$; $//$ Recursively copy left subtree

newNode$->$right $=$ copyTree$($sourceNode$->$right$)$; $//$ Recursively