Question

C++

Instantiate a binary search tree object and create such tree using elements of the sequence 8,3,10, 1,6,9, 14, 4,7, 13 with 8 as root of the tree. Find maximum and minimum elements of the tree, successor(10) and predecessor(13), print the inorder, postorder and preorder traversal of the tree.

Answer 1

Code:

#include <iostream>
using namespace std;
// Data structure to store a Binary Search Tree node
struct Node {
        int data;
        Node *left, *right;
};
// Function to create a new binary tree node having given key
Node* newNode(int key)
{
        Node* node = new Node;
        node->data = key;
        node->left = node->right = nullptr;
        return node;
}
// Recursive function to insert a key into BST
Node* insert(Node* root, int key)
{
        // if the root is null, create a new node and return it
        if (root == nullptr)
                return newNode(key);

        // if given key is less than the root node, recur for left subtree
        if (key < root->data)
                root->left = insert(root->left, key);

        // if given key is more than the root node, recur for right subtree
        else
                root->right = insert(root->right, key);

        return root;
}
void inorder(Node *root)     // to print inorder traversal of BST
{  
    if (root == NULL)  
        return;  

    inorder(root->left);  
    cout<< root->data << "   ";  
    inorder(root->right);  
} 
void preorder(Node *root)     // to print preorder traversal of BST 
{  
    if (root == NULL)  
        return;  
  
    cout<< root->data << "   ";
    preorder(root->left);  
    preorder(root->right);  
} 
void postorder(Node *root)    // to print postorder traversal of BST
{  
    if (root == NULL)  
        return;  
  
    postorder(root->left);
    postorder(root->right); 
    cout<< root->data << "   ";  
} 
Node* findMaximum(Node* root)   // function to find maximum value node in given BST
{
        while (root->right)
                root = root->right;
        return root;
}
Node* findMinimum(Node* root)   // function to find minimum value node in given BST
{
        while (root->left)
                root = root->left;
        return root;
}
void findPredecessor(Node* root, Node*& prec, int key)
{
        if (root == NULL) {
                prec = NULL;
                return;
        }
        if (root->data == key)     // if node with key's value is found, the predecessor is maximum value
        {                          // node in its left subtree (if any)
                if (root->left)
                        prec = findMaximum(root->left);
        }
        else if (key < root->data)   // if given key is less than the root node, recur for left subtree
        {
                findPredecessor(root->left, prec, key);
        }
        else            // if given key is more than the root node, recur for right subtree
        {
                prec = root;
                findPredecessor(root->right, prec, key);
        }
}
void findSuccessor(Node* root, Node*& succ, int key)
{
        // base case
        if (root == nullptr) {
                succ = nullptr;
                return;
        }
        if (root->data == key)    // if node with key's value is found, the successor is minimum value
        {                         // node in its right subtree (if any)
                if (root->right)
                        succ = findMinimum(root->right);
        }
        else if (key < root->data)     // if given key is less than the root node, recur for left subtree
        {
                succ = root;              // update successor to current node before recursing in left subtree
                findSuccessor(root->left, succ, key);
        }
        else                         // if given key is more than the root node, recur for right subtree
                findSuccessor(root->right, succ, key);
}
int main()
{

        int keys[] = {8,3,10,1,6,9,14,4,7,13};

        Node* root = nullptr;
        for (int key : keys)
                root = insert(root, key);
                
        cout<<"Maximum element in tree is : "<<(findMaximum(root))->data;
    cout<<"\nMinimum element in tree is : "<<(findMinimum(root))->data<<endl;
    
        cout << "\nInorder traversal of binary tree is \n"; 
    inorder(root);
    cout << "\nPreorder traversal of binary tree is \n"; 
    preorder(root);
    cout << "\nPostorder traversal of binary tree is \n"; 
    postorder(root);    
                
        Node* prec = nullptr;
        findPredecessor(root, prec, 13);
    cout << "\n\nPredecessor of node 13 : " <<prec->data << '\n';
    
    Node* succ = nullptr;
        findSuccessor(root, succ, 10);
    cout << "Successor of node 10 : " <<succ->data << '\n';
        return 0;
}

Output: