C++ program to construct binary search tree from its given level order traversal














































C++ program to construct binary search tree from its given level order traversal



Description:

The idea is to use a queue to construct tree. Every element of queue has a structure say NodeDetails which stores details of a tree node. The details are pointer to the node, and two variables min and max where min stores the lower limit for the node values which can be a part of the left subtree and max stores the upper limit for the node values which can be a part of the right subtree for the specified node in NodeDetails structure variable. For the 1st array value arr[0], create a node and then create a NodeDetails structure having pointer to this node and min = INT_MIN and max = INT_MAX. Add this structure variable to a queue. This Node will be the root of the tree. Move to 2nd element in arr[] and then perform the following steps:
  1. Pop NodeDetails from the queue in temp.
  2. Check whether the current array element can be a left child of the node in temp with the help of min and temp.node data values. If it can, then create a new NodeDetails structure for this new array element value with its proper %u2018min%u2019 and %u2018max%u2019 values and push it to the queue, make this new node as the left child of temp%u2019s node and move to next element in arr[].
  3. Check whether the current array element can be a right child of the node in temp with the help of max and temp.node data values. If it can, then create a new NodeDetails structure for this new array element value with its proper %u2018min%u2019 and %u2018max%u2019 values and push it to the queue, make this new node as the right child of temp%u2019s node and move to next element in arr[].
  4. Repeat steps 1, 2 and 3 until there are no more elements in arr[].

Program:

#include <bits/stdc++.h> 
#include<iostream>
using namespace std; 
struct Node 
{ 
    int data; 
    Node *left, *right; 
}; 
struct NodeDetails 
{ 
    Node *ptr; 
    int min, max; 
}; 
Node* getNode(int data) 
{ 
    Node *newNode = (Node*)malloc(sizeof(Node)); 
    newNode->data = data; 
    newNode->left = newNode->right = NULL;     
    return newNode; 
} 
Node* constructBst(int arr[], int n) 
{ 

    if (n == 0) 
        return NULL; 
      
    Node *root; 
    queue<NodeDetails> q; 
    int i=0; 
    
    NodeDetails newNode; 
    newNode.ptr = getNode(arr[i++]); 
    newNode.min = INT_MIN; 
    newNode.max = INT_MAX; 
    q.push(newNode); 
    
    root = newNode.ptr; 

    while (i != n)         
    { 

        NodeDetails temp = q.front(); 
        q.pop(); 
        if (i < n && (arr[i] < temp.ptr->data &&  
                          arr[i] > temp.min)) 
        { 
            newNode.ptr = getNode(arr[i++]); 
            newNode.min = temp.min; 
            newNode.max = temp.ptr->data; 
            q.push(newNode); 
            temp.ptr->left = newNode.ptr;             
        } 
        if (i < n && (arr[i] > temp.ptr->data && 
                               arr[i] < temp.max)) 
        { 
            newNode.ptr = getNode(arr[i++]); 
            newNode.min = temp.ptr->data; 
            newNode.max = temp.max; 
            q.push(newNode); 
            temp.ptr->right = newNode.ptr; 
        }         
    }
    return root; 
} 
void inorderTraversal(Node* root) 
{ 
    if (!root) 
        return; 
      
    inorderTraversal(root->left); 
    cout << root->data << " "; 
    inorderTraversal(root->right);     
} 
int main() 
{ 
    int arr[] = {7, 4, 12, 3, 6, 8, 1, 5, 10}; 
    int n = sizeof(arr) / sizeof(arr[0]); 
      
    Node *root = constructBst(arr, n); 
      
    cout << "Inorder Traversal: "; 
    inorderTraversal(root); 
    return 0;     
}  
Output:
Inorder Traversal: 1 3 4 5 6 7 8 10 12

More Articles of MAYANK KUMAR:

Name Views Likes
C++ program to remove all leaf nodes from the binary search tree 347 18
C++ program to find K%u2019th largest element in binary search tree when tree modification is not allowed 375 22
C++ program to find K%u2019th smallest element in binary search tree 356 24
C++ program to find second largest element in binary search tree 341 17
C++ program to find K%u2019th largest element in binary search tree 342 19
C++ program to check if each internal node of a binary search tree has exactly one child 319 12
C++ program to reverse a path in binary search tree using queue 347 19
C++ program to check if a binary tree is binary search tree or not 360 15
C++ program to find lowest Common Ancestor in a binary search tree 360 19
C++ program to binary Tree to binary search tree Conversion using std::Set 335 13
C++ program to merge Two binary search trees 367 17
C++ program to construct binary search tree from its given level order traversal 458 29
C++ program to convert a binary search tree to a Binary Tree 416 26
Difference between binary tree and binary search tree 432 26
C++ program to construct binary search tree from given inorder traversal 445 19
C++ program to convert binary tree to binary search tree 566 19
C++ Program to Print String 350 18
C++ Program to List Files in Directory 377 21
C++ Program to Delete Files 283 15
C++ Program to Get IP Address 384 24
C++ Program to Print Date and Time 331 11
C++ Program to Copy Files 338 19
C++ Program to Write to File 319 20
C++ Program to Read a File 322 19
C++ Program to Swap Two Variables 315 15
C++ Program to Find Largest of Two Number 373 20
C++ Program to Print Prime Numbers 364 20
C++ Program to Find Square Root of Number 322 15
C++ Program to Calculate Grade of Student 328 23
C++ Program to Calculate Average of Numbers 348 14
C++ Program to Calculate Average Percentage 298 15
C++ Program to Add Subtract Multiply Divide 324 24
C++ Program to Add Two Numbers 354 16
C++ Program to Get Input from User 310 18
C++ Program to Check Whether a String is Palindrome or Not 283 11
C++ Program to Find LCM 264 11
C++ Program to Convert Decimal to Binary Using Recursion 294 14
C++ Program to Find Factorial of Number Using Recursion 305 17
C++ Program to Find Sum of Natural Numbers Using Recursion 358 29
C++ Program to Find HCF or GCD 317 17
C++ Program to Find ASCII Value of Character 291 18
C++ Program to Find Numbers Divisible by Another Number 437 18
C++ Program to Find the Sum of Natural Numbers 270 17
C++ Program to convert Celsius to Fahrenheit 268 16
C++ Program to Check if a Number is Positive, Negative or 0 315 20
C++ Program to find square root of a number 294 19
C++ program for counting sort Algorithm 281 17
C++ programs for Bucket sort Algorithm 253 14
C++ program for Bubble sort 325 15

Comments