Question

Write a program to allow user to create a binary search tree. Your program should display...

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

Homework Answers

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 
Know the answer?
Your Answer:

Post as a guest

Your Name:

What's your source?

Earn Coins

Coins can be redeemed for fabulous gifts.

Not the answer you're looking for?
Ask your own homework help question
Similar Questions
Binary Search Tree Code in Java Write a program that prompts user to enter however many...
Binary Search Tree Code in Java Write a program that prompts user to enter however many numbers they want to add to the binary search tree. Then have the user input numbers until the tree contains that many elements. If the user enters a number that already exists in the tree, then a message should be displayed "Number is already in the tree". Once all elements are added to the tree print its contents in sorted order. Assume all user...
Write a C++ program that checks whether a binary search tree is an AVL. The input...
Write a C++ program that checks whether a binary search tree is an AVL. The input is an arbitrary binary search tree, and the output is binary, so either true or false.
In this lab, you will write a program that creates a binary search tree based on...
In this lab, you will write a program that creates a binary search tree based on user input. Then, the user will indicate what order to print the values in. **Please write in C code** Start with the bst.h and bst.c base code provided to you. You will need to modify the source and header file to complete this lab. bst.h: #ifndef BST_H #define BST_H typedef struct BSTNode { int value; struct BSTNode* left; struct BSTNode* right; } BSTNode; BSTNode*...
Given the list of values below, create a Binary Search Tree for the list, Use the...
Given the list of values below, create a Binary Search Tree for the list, Use the first value in the list as the root of the tree, add the nodes to BST in the order they appear in the list.[50, 44, 82, 39, 35, 98, 87, 100, 74, 23, 34, 14, 94] What is the minimum height of a Binary Tree that contains 24nodes? What is the minimum height of a Binary Tree that contains 64nodes? What is the minimum...
a) Design a recursive linear-time algorithm that tests whether a binary tree is a binary search...
a) Design a recursive linear-time algorithm that tests whether a binary tree is a binary search tree. Describe your algorithm in English or with a simple pseudocode program. b) (3 bonus pts.) Extend the algorithm in a) to test whether a binary tree is an AVL tree.
JAVA Write a program that has two functions in which the user chooses which one to...
JAVA Write a program that has two functions in which the user chooses which one to perform; 1. reads in a CSV file of integers into an array and insert it into a binary search tree class 2. deserializes an object and inserts it into a binary search tree class the tree class must be in a separate class from the CSV file read and deserialize object load
This program is in C++: Write a program to allow the user to: 1. Create two...
This program is in C++: Write a program to allow the user to: 1. Create two classes. Employee and Departments. The Department class will have: DepartmentID, Departmentname, DepartmentHeadName. The Employee class will have employeeID, emploeename, employeesalary, employeeage, employeeDepartmentID. Both of the above classes should have appropriate constructors, accessor methods. 2. Create two arrays . One for Employee with the size 5 and another one for Department with the size 3. Your program should display a menu for the user to...
‏What is the output of the Euler tour in the normal binary search tree if the...
‏What is the output of the Euler tour in the normal binary search tree if the key insert order is 5 , 2 , 8 , 5 , 9 , 5 , 1 , 3 , 4 , 2 , 8 ? All keys equal to the node should be the right subtree of that node. ____________________________________________________________ ‏Construct the binary max - heap for the keys given below. Once all the keys are inserted, perform the remove maximum operation, and...
Design a program that asks user to enter any three numbers. The program should display the...
Design a program that asks user to enter any three numbers. The program should display the three numbers in ascending order. using python code please
Write a program that asks the user for the name of a file. The program should...
Write a program that asks the user for the name of a file. The program should display only the first five lines of the file’s contents. If the file contains less than five lines, it should display the file’s entire contents. by python using while loop
ADVERTISEMENT
Need Online Homework Help?

Get Answers For Free
Most questions answered within 1 hours.

Ask a Question
ADVERTISEMENT