cs301 Assignment no 3 Solution Fall 2011

Question 1: Consider the following binary search tree (BST) and answer the questions given below.                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                         a)                  Write nodes after In-order traversing of tree. b)                  Write nodes after Post-order traversing of tree. c)                  Write nodes after Pre-order traversing of tree. d)                 What will be the resultant tree after insertion of nodes  8 & 21 Question 2: This question is the implementation of BST. Task: The code for BST is given in the lecture notes as also shown below class BinaryNode {   public:     Object getInfo();           void   setInfo(int object);           BinaryNode *   getLeft();           void   setLeft(BinaryNode *   left);           BinaryNode *   getRight();           void   setRight(BinaryNode *   right);    private:     int object;     BinaryNode *left;     BinaryNode *right;    // constructor     BinaryNode( int object, BinaryNode *LEFT, BinaryNode   *RIGHT ) : object( OBJECT ), left( LEFT ), right( RIGHT ) { } }; class BinarySearchTree {   public:     BinarySearchTree( ); // constructor.     ~BinarySearchTree( ); // destructor.     void insert( BinaryNode& node ) ;//insert the binary node in tree.     void remove( const string& x ); // remove a binary node from the tree.     const BinaryNode* find( const string& name ) const; // seach a node by name and return that node's address.     void print( ) const; // print the complete list in the tree.   private:     BinaryNode* root; }; Now using this code you are required to write some methods which are given below Ø  float avg(BinaryNode * rootNode) // Average of contents of all the nodes in the binary tree Ø  int depth(BinaryNode * rootNode) //  The depth/height of binary tree Ø  bool completeTree(BinaryNode * rootNode)  //Code to determine if a binary tree is strictly or complete binary tree.