Question

Write a program to allow user to create a binary search tree. Your program should display in BFT and DFT(in order) format.

Answer 1

Illustration to search 6 in below tree:
1. Start from root.
2. Compare the inserting element with root, if less than root, then recurse for left, else recurse for right.
3. If element to search is found anywhere, return true, else return false.

Insertion of a key
A new key is always inserted at leaf. We start searching a key from root till we hit a leaf node. Once a leaf node is found, the new node is added as a child of the leaf node.

         100                               100
        /   \        Insert 40            /    \
      20     500    --------->          20     500 
     /  \                              /  \  
    10   30                           10   30
                                              \   
                                              40

// C++ program to demonstrate insertion 
// in a BST recursively. 
#include <iostream> 
using namespace std; 

class BST 
{ 
        int data; 
        BST *left, *right; 

        public: 
        
        // Default constructor. 
        BST(); 
        
        // Parameterized constructor. 
        BST(int); 
        
        // Insert function. 
        BST* Insert(BST *, int); 
        
        // Inorder traversal. 
        void Inorder(BST *); 
}; 

// Default Constructor definition. 
BST :: BST() : data(0), left(NULL), right(NULL){} 

// Parameterized Constructor definition. 
BST :: BST(int value) 
{ 
        data = value; 
        left = right = NULL; 
} 

// Insert function definition. 
BST* BST :: Insert(BST *root, int value) 
{ 
        if(!root) 
        { 
                // Insert the first node, if root is NULL. 
                return new BST(value); 
        } 

        // Insert data. 
        if(value > root->data) 
        { 
                // Insert right node data, if the 'value' 
                // to be inserted is greater than 'root' node data. 
                
                // Process right nodes. 
                root->right = Insert(root->right, value); 
        } 
        else
        { 
                // Insert left node data, if the 'value' 
                // to be inserted is greater than 'root' node data. 
                
                // Process left nodes. 
                root->left = Insert(root->left, value); 
        } 
        
        // Return 'root' node, after insertion. 
        return root; 
} 

// Inorder traversal function. 
// This gives data in sorted order. 
void BST :: Inorder(BST *root) 
{ 
        if(!root) 
        { 
                return; 
        } 
        Inorder(root->left); 
        cout << root->data << endl; 
        Inorder(root->right); 
} 

// Driver code 
int main() 
{ 
        BST b, *root = NULL; 
        root = b.Insert(root, 50); 
        b.Insert(root, 30); 
        b.Insert(root, 20); 
        b.Insert(root, 40); 
        b.Insert(root, 70); 
        b.Insert(root, 60); 
        b.Insert(root, 80); 

        b.Inorder(root); 
        return 0; 
} 

BFT:

Algorithm:
For each node, first the node is visited and then it’s child nodes are put in a FIFO queue.

printLevelorder(tree)
1) Create an empty queue q
2) temp_node = root /*start from root*/
3) Loop while temp_node is not NULL
    a) print temp_node->data.
    b) Enqueue temp_node’s children (first left then right children) to q
    c) Dequeue a node from q and assign it’s value to temp_node

Implementation:
Here is a simple implementation of the above algorithm. Queue is implemented using an array with maximum size of 500. We can implement queue as linked list also.

/* C++ program to print level order traversal using STL */
#include <bits/stdc++.h> 
using namespace std; 

// A Binary Tree Node 
struct Node 
{ 
        int data; 
        struct Node *left, *right; 
}; 

// Iterative method to find height of Binary Tree 
void printLevelOrder(Node *root) 
{ 
        // Base Case 
        if (root == NULL) return; 

        // Create an empty queue for level order traversal 
        queue<Node *> q; 

        // Enqueue Root and initialize height 
        q.push(root); 

        while (q.empty() == false) 
        { 
                // Print front of queue and remove it from queue 
                Node *node = q.front(); 
                cout << node->data << " "; 
                q.pop(); 

                /* Enqueue left child */
                if (node->left != NULL) 
                        q.push(node->left); 

                /*Enqueue right child */
                if (node->right != NULL) 
                        q.push(node->right); 
        } 
} 

// Utility function to create a new tree node 
Node* newNode(int data) 
{ 
        Node *temp = new Node; 
        temp->data = data; 
        temp->left = temp->right = NULL; 
        return temp; 
} 

// Driver program to test above functions 
int main() 
{ 
        // Let us create binary tree shown in above diagram 
        Node *root = newNode(1); 
        root->left = newNode(2); 
        root->right = newNode(3); 
        root->left->left = newNode(4); 
        root->left->right = newNode(5); 

        cout << "Level Order traversal of binary tree is \n"; 
        printLevelOrder(root); 
        return 0; 
} 

Output:

Level order traversal of binary tree is - 
1 2 3 4 5