CMSC 341Binary Search TreeBST ImplementationBinarySearchTree classBinarySearchTree class (cont)BinarySearchTree ImplementationPerformance of findPredecessor in BSTSuccessor in BSTThe remove OperationThe insert OperationImplementation of makeEmptyTree IteratorsTree Iterator ImplementationTree Iterators (cont)Tree Iterators (cont’d)Slide 1701/14/19 1CMSC 341Binary Search Trees01/14/19 2Binary Search TreeA Binary Search Tree is a Binary Tree in which, at every node v, the value stored in the left child node is less than the value at v and the value stored in the right child is greater.The elements in the BST must be comparable.Duplicates are not allowed.01/14/19 3BST ImplementationThe SearchTree ADT–A search tree is a binary search tree in which are stored homogeneous elements with no duplicates.–It is dynamic.–The elements are ordered in the following ways•inorder -- as dictated by operator<•preorder, postorder, levelorder -- as dictated by the structure of the tree–Each BST maintains a simple object, known as ITEM_NOT_FOUND, that is guaranteed to not be an element of the tree. ITEM_NOT_FOUND is provided to the constructor. (author’s code)01/14/19 4BinarySearchTree classtemplate <class Comparable>class BinarySearchTree {public:BinarySearchTree(const Comparable &notFnd);BinarySearchTree (const BinarySearchTree &rhs);~BinarySearchTree();const Comparable &findMin() const;const Comparable &findMax() const;const Comparable &find(const Comparable &x) const;bool isEmpty() const;void printTree() const;void makeEmpty();void insert (const Comparable &x);void remove (const Comparable &x);const BinarySearchTree &operator=(const BinarySearchTree &rhs);01/14/19 5BinarySearchTree class (cont)private:BinaryNode<Comparable> *root;const Comparable ITEM_NOT_FOUND;const Comparable&elementAt(BinaryNode<Comparable> *t) const;void insert (const Comparable &x,BinaryNode<Comparable> * &t) const;void remove (const Comparable &x, BinaryNode<Comparable> * &t) const;BinaryNode<Comparable> *findMin(BinaryNode<Comparable> *t const;BinaryNode<Comparable>*findMax(BinaryNode<Comparable> *t)const;BinaryNode<Comparable>*find(const Comparable &x, BinaryNode<Comparable> *t) const;void makeEmpty(BinaryNode<Comparable> *&t) const;void printTree(BinaryNode<Comparable *t) const;BinaryNode<Comparable> *clone(BinaryNode<Comparable> *t)const;};6BinarySearchTree Implementationtemplate <class Comparable>const Comparable &BinarySearchTree<Comparable> ::find(const Comparable &x) const {return elementAt(find (x, root));}template <class Comparable>const Comparable &BinarySearchTree<Comparable> ::elementAt(BinaryNode<Comparable> *t) const {return t == NULL ? ITEM_NOT_FOUND : t->element;}template <class Comparable>BinaryNode<Comparable> *BinarySearchTree<Comparable> ::find(const Comparable &x, BinaryNode<Comparable> *t) const{if (t == NULL) return NULL;else if (x < t->element) return find(x, t->left);else if (t->element < x) return find(x, t->right);else return t; // Match}01/14/19 7Performance of findSearch in randomly built BST is O(lg n) on average–but generally, a BST is not randomly builtAsymptotic performance is O(h) in all cases01/14/19 8Predecessor in BSTPredecessor of a node v in a BST is the node that holds the data value that immediately precedes the data at v in order.Finding predecessor–v has a left subtree•then predecessor must be the largest value in the left subtree (the rightmost node in the left subtree)–v does not have a left subtree•predecessor is the first node on path back to root thatdoes not have v in its left subtree01/14/19 9Successor in BSTSuccessor of a node v in a BST is the node that holds the data value that immediately follows the data at v in order.Finding Successor–v has right subtree•successor is smallest value in right subtree (the leftmost node in the right subtree)–v does not have right subtree•successor is first node on path back to root that does not have v in its right subtree10The remove Operationtemplate <class Comparable>void BinarySearchTree<Comparable>::remove(const Comparable &x, BinaryNode<Comparable> *&t) const{if (t == NULL)return; // item not found, do nothingif (x < t->element)remove(x, t->left);else if (t->element < x)remove(x, t->right);else if ((t->left != NULL) && (t->right != NULL)) {t->element = findMin( (t->right)->element );remove (t->element, t->right);}else {BinaryNode<Comparable> *oldNode = t;t = (t->left != NULL) ? T->left : t->right;delete oldNode;}}11The insert Operationtemplate <class Comparable> void BinarySearchTree<Comparable>::insert(const Comparable &x) // public insert( ){insert (x, root); // calls private insert( )}template <class Comparable>void BinarySearchTree<Comparable>::insert(const Comparable &x, BinaryNode<Comparable> *&t) const{if (t == NULL)t = new BinaryNode<Comparable>(x, NULL, NULL);else if (x < t->element)insert (x, t->left);else if (t->element < x)insert (x, t->right);else; // Duplicate; do nothing}01/14/19 12Implementation of makeEmptytemplate <class Comparable>void BinarySearchTree<Comparable>::makeEmpty() // public makeEmpty (){makeEmpty(root); // calls private makeEmpty ( )}template <class Comparable>void BinarySearchTree<Comparable>::makeEmpty(BinaryNode<Comparable> *&t) const {if (t != NULL) { // post order traversalmakeEmpty (t->left);makeEmpty (t->right);delete t;}t = NULL;}01/14/19 13Tree IteratorsCould provide separate iterators for each desired order–Iterator<T> *GetInorderIterator();–Iterator<T> *GetPreorderIterator();–Iterator<T> *GetPostorderIterator ();–Iterator<T> *GetLevelorderIterator ();01/14/19 14Tree Iterator ImplementationApproach 1: Store traversal in list.Return list iterator for list.Iterator<T> BinaryTree::GetInorderIterator() {List<T> *lst = new ArrayList<T>;FullListInorder(list, getRoot());return list->GetIterator();}void FillListInorder(ArrayList<T> *lst, Bnode<T> *node){if (node == NULL) return;FillListInorder(list, node->left);lst->Append(node->data);FillListInorder(lst, node->right); }01/14/19 15Tree Iterators (cont)Approach 2: store traversal in stack to mimic recursive traversaltemplate <class T>class InOrderIterator : public Iterator{private:Stack<T> _stack;BinaryTree<T> *_tree;public:InOrderIterator(BinaryTree<T> *t);bool hasNext() {return (!_stack.isEmpty()); }T Next();};01/14/19 16Tree Iterators (cont’d)template <class T>InOrderIterator<T>::InOrderIterator(BinaryTree<T> *t) { _tree = t;Bnode<T> *v = t->getRoot();while (v != NULL) {_stack.Push(v); // push