online advertising

Sunday, November 27, 2016

HackerRank - Binary Search Tree : Insertion

Problem:

Please find the problem here.

Solution: 

Note the recursive solution - the given function prototype basically asked for it!

Code:

#include "stdafx.h"

// https://www.hackerrank.com/challenges/binary-search-tree-insertion

#include "HACKER_RANK_BINARY_SEARCH_TREE_INSERTION.h"
#include <map>
#include <iostream>
#include <sstream>
#include <vector>
#include <string>

using namespace std;

namespace _HACKER_RANK_BINARY_SEARCH_TREE_INSERTION
{
    typedef struct node
    {
        int data;
        node * left;
        node * right;
    } node;

    node * insert(node * root, int value)
    {
        if (root == nullptr)
        {
            node* new_node = new node();
            new_node->data = value;
            new_node->left = nullptr;
            new_node->right = nullptr;
            return new_node;
        }
        else
        {
            if (value < root->data)
            {
                root->left = insert(root->left, value);
            }
            else
            {
                root->right = insert(root->right, value);
            }
            return root;
        }
    }
};

using namespace _HACKER_RANK_BINARY_SEARCH_TREE_INSERTION;

int HACKER_RANK_BINARY_SEARCH_TREE_INSERTION()
{
    node a;
    node b;
    node c;
    node d;
    node e;
    a.data = 4;
    b.data = 2;
    c.data = 7;
    d.data = 1;
    e.data = 3;
    a.left = &b;
    a.right = &c;
    b.left = &d;
    b.right = &e;
    c.left = nullptr;
    c.right = nullptr;
    d.left = nullptr;
    d.right = nullptr;
    e.left = nullptr;
    e.right = nullptr;
    node* f = insert(&a, 6);
    cout << f->right->left->data << endl;
    return 0;
}

No comments :

Post a Comment