Question

Build a binary search tree with the following words. Insert them in an order so that the tree has as small a depth as possible. (Consider the insertion order of the words) Print the tree after,also, any, back, because, come, day, even, first, give, how, its, look, most, new, now, only, other, our, over, than, then, these, think, two, us, use, want, way, well, work.

C++

Answer 1

Hi,

To implement a Binary Search Tree, we'll need to do the following:

• Create a struct bst which will have a data variable(string type in our case) that hold the value of each node and two pointer variables left and right that will point to the left subtree and right subtree of a node.
• Now, that was just a definition of nodes in our tree. Before we actually move to the add node part, let's discuss what we can add to the tree. We can only add nodes of type bst(the struct we created above), but we are provided strings which are only data part of the struct. To do this we will convert the strings into type bst with both left and right pointers pointing to null. We will implement this using our newNode() method which takes a sring input and return a bst node.
• Now we can use the returned bst node from newNode() method to add it to the tree. We will compare the value with the root node passed into the function and if the string is smaller we will pass it to the left sub tree else to the right sub tree and call insertNode() function again until we reach a null node and there we will insert the node to be inserted. since we're comparing in every recursion, the node will keep travesing through sub tress and sub-sub trees and so on until it reaches it's appropriate spot.
• For printing the tree, we will start from root node and print it. and move to the lower nodes recursively. If the lower node is on the left side of the tree we will add prefix "|--" and if it's on the right side of tree we will add prefix "|->". We will call recursion on left node first so the left subtree will be printed first and then we will call recursion on right node of the root to print the right subtree below the left subtree.
• And for the last part, the order of insertion, we know that for minimum height of tree both the left and right subtrees of the root node should be balanced which means the both will have almost equal number of nodes on each side. For this to happen the root value should be the middle value of all nodes, i.e there should be almost same number of nodes smaller than root as the number of nodes greater than root. And this logic shall follow in the left and right sub trees of the root node as well i.e, the root of left sub tree will be the middle value of all the values in the left sub tree and so will this logic follow in the sub-sub trees and so on. Thus, to do so we will start adding the middle value of all the inputs to the root and then we will recursivley repeat the same for left and right sub trees. This is similar to binary searching where we keep on checking the middle value of a group and the middle values of the sub groups and then the sub sub groups and so on.
• Also, we have an added advatage of the input because it is already provided in the sorted manner. Thus, we do not have to sort it.

Here's the code:

#include<iostream>
#include<string.h>
#include<cstdlib>
using namespace std;
  

struct bst //our bst struct that defines a node
{
string data;
struct bst *left, *right;
};
  

struct bst *newNode(string key) //to create a new node from a key
{
struct bst *temp = new struct bst();
temp->data = key;
temp->left = temp->right = NULL; //left and right of the new node are set null and are later updated when we add any node to it's left or right side.
return temp;
}

struct bst* insertNode(struct bst* node, string key) //to insert a new node in the binary search tree
{
  
if (node == NULL)
   return newNode(key); //if the node is, we basically just have to create a new node because here the value is supposed to be actually inserted.

//if tree is not empty find the proper place to insert new node
if (key < node->data) //if key is smaller move to the left sub tree
   node->left = insertNode(node->left, key); //keep looking in the subtrees until right location is reached
else
   node->right = insertNode(node->right, key); //we move to right sub tree if key is bigger than root passed

  
return node; //return the node after adding the new key
}
  
void printBT(string prefix, bst* node, int isLeft)
{
if( node != NULL )
{
       cout<<prefix;
cout << (isLeft ? "|--" : "|->" );   //this will print |-- for left node and |-> for right node

  
cout << node->data << endl;   //after the prefix we can print value

printBT( prefix+(isLeft ? "| " : " "), node->left, 1);   //pass 1 for isLeft arguement for the left node after adding some appropriate prefix acc to the current node.
printBT( prefix+(isLeft ? "| " : " "), node->right, 0);//pass 0(false) for isLeft arguement for right node
}
}

void insert(bst *& root, string values[], int start, int end){   //to insert nodes in appropriate manner
  
       if(start<=end){   //similar condition to binary search
  
       int mid = (end+start)/2;   // take the mid of all values
  
       root = insertNode(root,values[mid]);   //add the value to the root
       insert(root,values,start,mid-1);   //repeat the same for left sub tree
       insert(root,values,mid+1,end);   //repeat the same for right sub tree
}
}

int main()
{
string words[] = {"after","also", "any", "back", "because", "come", "day", "even", "first", "give", "how", "its", "look", "most", "new", "now", "only", "other", "our", "over", "than", "then", "these", "think", "two", "us", "use", "want", "way", "well", "work"};
struct bst *root = NULL; //our tree
int length =sizeof(words)/sizeof(words[0]);   //to find length of input string array
insert(root,words,0,length-1);   //insert elements
cout<<"Binary Search Tree created:"<<endl;
printBT("", root, 0); //print the tree

return 0;
}

Sample Output:

You can see that in the tree only 5 levels(maximum) are there in any sub tree of the tree and considering the input of 31 values it can be theoretically verified using the formula floor(log2(N))+1 which when we put N=31 gives 5.

That's all. Please leave an upvote if you found it helpful, I hope it helped!