Simple BST implementation using C++ Struct

Question

I am trying to implement DSs in C++ and this is BST insert and search functions. I tried in two different ways, please review and see if one is advantageous over other.
With pointer to pointer

#include <stdio.h>
#include <iostream>

struct BstNode{
 int data;
 BstNode* left;
 BstNode* right;
};

BstNode* NewNode(int data)
{
 BstNode* newNode = new BstNode();
 newNode->data = data;
 newNode->left = NULL;
 newNode->right = NULL;
 return newNode;
}
void Insert(BstNode** root,int data)
{
 if(*root == NULL)
 {
     *root= NewNode(data);
 }
 else if(data <= (*root)->data)
 {
     (*root)->left = NewNode(data);
 }
 else
 {
     (*root)->right = NewNode(data);
 }
}
bool SearchBST(BstNode* root, int data)
{
 if(root == NULL)
 {
     return false;
 }
 else if(root->data == data)
 {
     return true;
 }
 else if(data <= root->data)
 {
     return SearchBST(root->left, data);
 }
     else
     {
         return SearchBST(root->right, data);
     }
 }
 int main()
 {
     BstNode* ptr_root = NULL;
     Insert(&ptr_root,15);
     Insert(&ptr_root,10);
     Insert(&ptr_root,16);
     int num;
     std::cout<<"Enter the number: \n";
     std::cin>> num;
     if (SearchBST(ptr_root,num))
         std::cout<<"Found\n";
     else
         std::cout<<"Not Found\n";

     return 0;
 }

Without pointer to a pointer:

#include <stdio.h>
#include <iostream>

struct BstNode{
    int data;
    BstNode* left;
    BstNode* right;
};
BstNode* NewNode(int data)
{
    BstNode* newNode = new BstNode();
    newNode->data = data;
    newNode->left = NULL;
    newNode->right = NULL;
    return newNode;
}
BstNode* Insert(BstNode* root,int data)
{
    if(root == NULL)
    {
        root= NewNode(data);
    }
    else if(data <= root->data)
    {
        root->left = NewNode(data);
    }
    else
    {
        root->right = NewNode(data);
    }
    return root;
}
bool SearchBST(BstNode* root, int data)
{
    if(root == NULL)
    {
        return false;
    }
    else if(root->data == data)
    {
        return true;
    }
    else if(data <= root->data)
    {
        return SearchBST(root->left, data);
    }
    else
    {
        return SearchBST(root->right, data);
    }
}
int main()
{
    BstNode* ptr_root = NULL;
    ptr_root=Insert(ptr_root,15);
    ptr_root=Insert(ptr_root,10);
    ptr_root=Insert(ptr_root,16);
    int num;
    std::cout<<"Enter the number: \n";
    std::cin>> num;
    if (SearchBST(ptr_root,num))
        std::cout<<"Found\n";
    else
        std::cout<<"Not Found\n";

    return 0;
}

Answer 1

Neither of your implementations is "advantageous" over other because both of them are C-style, unidiomatic C++ code — they are really C code with a handful of C++ additions. Moreover, they share many errors. This review will (hopefully) help you convert your code to C++ style and fix these errors.

Formatting

The indentation of the first implementation is a nightmare. Fix it by consistently indenting everything by 4 spaces and make sure lines on the same indentation level align with each other. Also, comma tokens should generally be followed by a space.

General design

You code does not provide a suitable interface because "BST Node" is an implementation detail. Users do not want to work directly with nodes most of the time; they want to work with the trees. Therefore, you should provide a class to encapsulate the tree. The insert and search functions should be member functions of the tree, not free functions.

Memory management

You use new to allocate nodes, but never delete them. In other words, you are constantly leaking memory. This makes your code not reusable. You should use a smart pointer (e.g., std::unique_ptr) instead of raw pointers in order to solve this problem.

Miscellaneous

#include <stdio.h> is redundant and should be removed.

Instead of the type-unsafe NULL, use nullptr.

---

Here's how I'd put the whole thing together (minimal version):

#include <initializer_list>
#include <iostream>
#include <memory>

class Binary_search_tree {
    struct Node {
        int value{};
        std::unique_ptr<Node> left{};
        std::unique_ptr<Node> right{};
    };
public:
    Binary_search_tree() = default;
    Binary_search_tree(std::initializer_list<int> init)
    {
        for (auto elem : init) {
            insert(elem);
        }
    }
    void insert(int value)
    {
        insert_at(root, value);
    }
    bool contains(int value) const
    {
        return contains_at(root, value);
    }
private:
    void insert_at(std::unique_ptr<Node>& node, int value)
    {
        if (!node) {
            node.reset(new Node{value});
        } else if (value < node->value) {
            insert_at(node->left, value);
        } else {
            insert_at(node->right, value);
        }
    }
    bool contains_at(const std::unique_ptr<Node>& node, int value) const
    {
        if (!node) {
            return false;
        } else if (value < node->value) {
            return contains_at(node->left, value);
        } else if (node->value < value) {
            return contains_at(node->right, value);
        } else {
            return true;
        }
    }
    std::unique_ptr<Node> root{};
};

int main()
{
    Binary_search_tree tree{31, 41, 59, 26, 53, 59};

    int num;
    std::cout << "Enter the number: \n";
    std::cin >> num;

    if (tree.contains(num)) {
        std::cout << "Found\n";
    } else {
        std::cout << "Not Found\n";
    }

    return 0;
}

(live demo)