DSA Assignment Using File Handling

Question:

Applying the concepts of Binary Search Tree data structure, write a program that constructs a BST from contents of attached “dictionary.txt” file. Next a word need to be taken as input from the user and search for it in the tree to see if it is spelled correctly. Perform spell checking using BST multiple times till user enters “End/end” that should be considered as sentinel value. In case the user has spelled the word correctly, display a message like “Match found at Depth 5 (or any other appropriate depth) inside tree”. Also display Balance-Factor (BF) of the node where match was found. [Note – You are not supposed to save height of each node but rather compute BF once match is found]. In case no match found, display appropriate message.

Code:

The below is the code for DSA  Assignment Using File Handling

using namespace std;

class TreeNode
{
public:
string data;
TreeNode* left;
TreeNode* right;
};

class tree{
public:
TreeNode *root;

    tree(){root=NULL;}

void insertNode(TreeNode*& root, string data)
{

if (root == NULL) 
{
  root = new TreeNode;
  root->data = data;
  root->left = NULL;
  root->right = NULL;
} 
else if (data < root->data) 
{
  insertNode(root->left, data);
} 
else
{
  insertNode(root->right, data);
}

}

void display(TreeNode* root)
{
if (root!=NULL)
{
display(root->left);
cout<data<<" "; display(root->right);
}
}

};

TreeNode* search(TreeNode* root, string name, int &dept)
{

  if (root == NULL) 
  {
    return NULL;
  } 
  else if (name == root->data) 
  {
    return root;
  } 
  else if (name < root->data) 
  {
    dept++;
    return search(root->left, name, dept);
  } 
  else 
  {
    dept++;
    return search(root->right, name, dept);
  }

}

int getHeight(TreeNode* node)
{
if (node == NULL)
return 0;
return 1 + max(getHeight(node->left), getHeight(node->right));
}

int getBalanceFactor(TreeNode* node)
{
if (node == NULL)
return 0;
return (getHeight(node->left) - getHeight(node->right));
}

int main()
{

tree t;
ifstream input("dictionary.txt");

string name;
while (input >> name) {
t.insertNode(t.root, name);
}
string word;

// t.display(t.root);

while(1)
{
    cout<<"\n\nENTER A WORD TO SEARCH FROM THE DICTIONARY: ";
    cin>>word;
    int depth = 0;
    TreeNode *found = search(t.root,word,depth);
    int balance_factor = getBalanceFactor(found);
    if (word=="end" || word=="End")
    break;

    if (found == NULL) 
    {
        cout<<"\n\n";
        cout << word << " was not found in the tree "<< endl;
    } 
    else 
    {
        cout<<"\n\n";
        cout << word << " was found in the tree at depth " <<depth<< endl;
        cout  << "\nThe balancing factor of the  "<< word<<" is "<<balance_factor<< endl;
    }

}

  return 0;

}

For more details about Huffman coding click here

For other assignments and quizzes click here 

Output: