Program to set up a binary tree, print it & search - Node Class C++

Question

I have created a program which contains a class Node, for representing a binary tree of any type(template).

In my Node.h class, I have two constructors, however I am not sure if I implemented both of them correctly. Initialising the values within the constructors has confused me. In my main.cpp file, I have a setUpTree function. My program executes now, but doesnt print the tree that is set up.

I have tried for hours trying to fix this but to no ends. I am not really experienced with C++, pointers, constructors etc yet.

I would appreciate it if anyone could help me fix my code so that the setUpTree function works, and also the printTree method.

Thanks

Node.h Class:

   #ifndef NODE_H
#define NODE_H
#include <iostream>
#include <string>
using namespace std;

//an object of type node holds 3 things
// - an item (of type t)
// - a left subtree
// - a right subtree

template<typename T>
class Node {
public:
    Node(T item); //constructor to create a leaf node
    Node(T item, Node *lft, Node *rht); //constructor which creates an internal node 
    ~Node(); //Destructor

    //public data member functions:
    bool searchTree(T key);
    void printTree();

private:
    //private data member functions:
    Node* left;
    Node* right;
    T item;
};

//constructor 
template<typename T>
Node<T>::Node(T i, Node<T> *lft, Node<T> *rht) {
    item = i;
    left = NULL;
    right = NULL;
}

//constructor 
template <typename T>
Node<T>::Node(T i) { //should i be a parameter here?
    item = i; //is this right for this constructor?
}

//destructor
template <typename T>
Node<T>::~Node() {
    delete left;
    delete right;
    //delete;
}


//print tree method
template <typename T>
void Node<T>::printTree() {
    if (left != NULL) {
        left->printTree();
        cout << item << endl;//alphabetical order
    }

    if (right != NULL) {
        right->printTree();
        //cout << item << endl; //post order
    }
}

//search Tree method
template <typename T>
bool Node<T>::searchTree(T key) {
    bool found = false;
    if (item == key) {
        return true;
    }
    if (left != NULL) {
        found = left->searchTree(key);
        if (found) return true;
    }
    if (right != NULL) {
        return right->searchTree(key);
    }
    return false; //if left and right are both null & key is not the search item, then not found == not in the tree.
}

#endif

Main.cpp Class:

#include "Node.h"
#include <iostream>
using namespace std;

//set up tree method
Node<string> *setUpTree() {
    Node<string> *s_tree =
        new Node<string>("Sunday",
        new Node<string>("monday",
        new Node<string>("Friday"),
        new Node<string>("Saturday")),
        new Node<string>("Tuesday",
        new Node<string>("Thursday"),
        new Node<string>("Wednesday")));
    return s_tree;
}

int main() {

    Node<string> *s_tree;
    s_tree = setUpTree(); //call setUpTree method on s_tree

    cout << "Part 2 :Printing tree values: " << endl;
    s_tree->printTree(); //call print tree method

    cout << endl;

    //search for range of tree values
    //searchTree(s_tree, "Sunday");
    //searchTree(s_tree, "Monday");

    return 0;
}

Answer 1

First the return in setupTree should be s_tree.

Second you construct a binary tree by adding each item one at a time. I would suggest making setupTree accept an array of values that you can then take one at a time and build the tree.

As was pointed out the default values for left and right should be NULL. However, I would just do it in the declaration, so that you don't have to repeat it in every constructor where the values aren't specified:

private:
    //private data member functions:
    Node* left = NULL;
    Node* right = NULL;
    T item;

Answer 2

I don't know if it's the only problem but... if you construct a leaf, you have to set left and right pointers to NULL

template <typename T>
Node<T>::Node(T i) : left(NULL), right(NULL), item(i)
 { }

otherwise, when the destructor is called

template <typename T>
Node<T>::~Node() {
    delete left;
    delete right;
    //delete;
}

delete is called over undefined values; two times.

It's a perfect recipe for a crash.

Other problems in every point you use left or right checking if the pointer is NULL, as made in printTree() or searchTree(): the value is undefined, so can be non NULL, pass the test and printTree() is called over a pointer with an undefined value

-- EDIT --

Suggested contructors.

template <typename T>
Node<T>::Node (T i, Node<T> * lft, Node<T> * rht)
 : left(lft), right(right), item(i)
 { }

template <typename T>
Node<T>::Node (T i)
 : left(NULL), right(NULL), item(i)
 { }

--- EDIT 2 ---

it is now printing some values at least ; monday sunday tuesday. not sure about the rest

Look at your printTree() metod

template void Node::printTree() { if (left != NULL) { left->printTree(); cout << item << endl;//alphabetical order }

if (right != NULL) {
    right->printTree();
    //cout << item << endl; //post order
}

}

It print the value (item) only if left isn't NULL. So it doesn't print the value of the leafs.

Suggestion: modify printTree() to print item even when left is NULL.

By example

template <typename T>
void Node<T>::printTree() {
    if (left != NULL) {
        left->printTree();
    }

    cout << item << endl;

    if (right != NULL) {
        right->printTree();
    }
}