CODEWITHSUNDEEP
c++c++11pointersreference
user3139545
user3139545

Reputation: 7374

Binary search tree in C++ with leaves as null values not working with reference parameters

Im trying to write a simple function to decide in a binary tree is also a binary search tree as a way to learn C++. However the first problem I found was to define the end leafs in my recursive Node struct.

#include <iostream>
#include <map>
#include <string>

struct Node {
    int data;
    Node* left;
    Node* right;
};
Node CreateNode(const int data, const Node& left, const Node& right) {
    Node node;
    node.data = data;
    node.left -> left;
    node.right -> right;
    return node;
}

int main(int argc, const char * argv[]) {
    auto root = CreateNode(1, NULL, NULL);
    isBST(&root);

    return 0;
}

bool isBST(Node* root) {

}

A solution would be to use pointers instead as parameters to CreateNode but I dont want to do that since C++11 recommends to replace pointer parameters with reference parameters.

My questions is how can I define leaves in my code above since I cant just make them null pointers as I would if my parameters would have been pointers.

Update: The isBST has a parameter as pointer only because I want to mix it up to understand the difference.

Upvotes: 0

Views: 293

Answers (1)

user7860670
user7860670

Reputation: 37487

References are not really suitable in this context because they imply no ownership transfer and no optional supply. Another approach will be to use smart pointers. 

#include <memory>
#include <utility>

struct Node;

using UniqueNode = ::std::unique_ptr<Node>;

struct Node 
{
   int data;
   UniqueNode left;
   UniqueNode right;

   explicit Node(void): data{} {}

   explicit Node(int const init_data, UniqueNode init_left, UniqueNode init_right)
   :   data{init_data}
   ,   left{::std::move(init_left)}
   ,   right{::std::move(init_right)}
   {}
};

// no need to manually write create function...
// UniqueNode CreateNode(const int data, UniqueNode left, UniqueNode right) 

int main(int argc, const char * argv[]) {
   UniqueNode root{::std::make_unique<Node>(42, nullptr, nullptr)};
   isBST(*root);

  return 0;
}

// takes a reference because no ownership is transferred, probably should be a member funciton
bool isBST(Node & root) {

}

Upvotes: 1

Related Questions