Inorder, Preorder, and Postorder traversal of a binary tree in C++

Question

I am a newbie in this world of data structures and algorithms (returning to these topics after 5 long years). Can someone please check if the code I have written for Binary Tree is OK?

Test-case 10, 3,11,11,5,0

PrintInorder 3,0,5,10,11,11

PrintPreOrder 10,3,0,5,11,11

PrintPostOrder 3,0,5,11,11,10

using namespace std;

template<typename T>
struct Node
{
    T data;
    Node<T>* left;
    Node<T>* right;

    Node()
    {
        left = nullptr;
        right = nullptr;
    }
};

template<typename T>
class BTree
{
public:
    BTree();
    ~BTree();
    void Add(T val);
    void Print(int o);
    T Find(T key);
private:
    Node<T>* root;
    Node<T>* temp;
    int height;
    Node<T>* Add(T val, Node<T>* node);
    void PrintInorder(Node<T>* ptr);
    void PrintPreOrder(Node<T>* ptr);
    void PrintPostOrder(Node<T>* ptr);
};

template<typename T>
T BTree<T>::Find(T key)
{
    Node<T>* current = this->root;

    while (current!= nullptr)
    {
        if (current->data == key)
        {
            return current->data;
        }
        else if(current->data > key)
        {
            current = current->left;
            continue;
        }
        else if (current->data < key)
        {
            current = current->right;
            continue;
        }
    }
}

template<typename T>
void BTree<T>::PrintInorder(Node<T>* ptr)
{
    PrintPreOrder(ptr->left);
    cout<<ptr->data<<endl;
    PrintPreOrder(ptr->right);
}

template<typename T>
void BTree<T>::PrintPostOrder(Node<T>* ptr)
{
    PrintPreOrder(ptr->left);
    PrintPreOrder(ptr->right);
    cout<<ptr->data<<endl;
}

template<typename T>
BTree<T>::BTree()
{
    root = nullptr;
    height = 0;
}

template<typename T>
void BTree<T>::PrintPreOrder(Node<T>* ptr)
{
    if (ptr!=nullptr)
    {
        cout<<ptr->data<<endl;
    }

    if(ptr->left!=nullptr)
        PrintPreOrder(ptr->left);
    if(ptr->right!=nullptr)
        PrintPreOrder(ptr->right);
}

template<typename T>
void BTree<T>::Print(int o)
{
    if (o==1)
    {
        PrintInorder(root);
    }
    else if (o==2)
    {
        PrintPreOrder(root);
    }
    else if(o==3)
    {
        PrintPostOrder(root);
    }
}

template<typename T>
BTree<T>::~BTree()
{
}

template<typename T>
void BTree<T>:: Add(T val)
{
    if (root==nullptr)
    {
        root = Add(val, nullptr);
    }
    else
    {
        root = Add(val,root);
    }
}

template<typename T>
Node<T>* BTree<T>::Add(T val, Node<T>* node)
{
    if (node == nullptr)
    {
        node = new Node<T>();
        node->data = val;
        return node;
    }
    else
    {
        if (val <= node->data)
        {
            node->left = Add(val,node->left);
        }
        else
        {
            node->right =  Add(val,node->right);
        }
    }

    return node;
}

Answer 1

I can see a few changes that at least might be worth considering.

Minimize Requirements

All else being equal, you typically want to minimize the requirements you place on the type contained in a container like this. For example, where you need to do comparisons, you can use the same operator (typically <) to do all the comparisons. For example, in your Find, we can do just a little rearranging to get this:

template<typename T>
T BTree<T>::Find(T key)
{
    Node<T>* current = this->root;

    while (current!= nullptr)
    {
        if (current->data < key)
            current = current->right;
        else if (key < current->data)
            current = current->left;
        else // Neither is less than the other, so they must be equal
            return current->data;
    }
}

With this, T only needs to define "less than" for our code to work (where it previously required <, > and ==).

Check recursion

Your PrintInOrder looks broken:

template<typename T>
void BTree<T>::PrintInorder(Node<T>* ptr)
{
    PrintPreOrder(ptr->left);
    cout<<ptr->data<<endl;
    PrintPreOrder(ptr->right);
}

This seems to do a pre-order traversal of the left sub-tree, prints the current, then a pre-order traversal of the right sub-tree. For in-order, you want an in-order traversal of the left-subtree, process the current node, then in-order traversal of the right subtree. With only a few nodes (so the tree is never very deep) this probably may not be visible, but it's clearly wrong.

The same applies to your PrintPostOrder.

Simplify where possible

At least to me, your PrintPreOrder seems unnecessarily complex. I'd do something like:

template <class T>
void PrintPreOrder(Node<T> *ptr) { 
    if (ptr == nullptr)
        return;

    std::cout << ptr->data << "\n";
    PrintPreOrder(ptr->left);
    PrintPreOrder(ptr->right);
}

With this we only do one check for a null pointer in one place.

Likewise, your Add currently looks like this:

template<typename T>
void BTree<T>:: Add(T val)
{
    if (root==nullptr)
    {
        root = Add(val, nullptr);
    }
    else
    {
        root = Add(val,root);
    }
}

This checks whether root is a null pointer, and if it is it explicitly passes a null pointer. Otherwise, it pass root. If we just pass root, (whether it's a null pointer or not) we get exactly the same effect.

template<typename T>
void BTree<T>:: Add(T val)
{
    Add(val, root);
}

Avoid std::endl

When people use std::endl, they typically just want to write a new-line to a stream. Unfortunately, that's not quite all that std::endl actually does--in addition to writing the new-line, it flushes the stream. Flushing the stream unnecessarily can lead to a dramatic speed loss (e.g., 10x is pretty common).

On the rare occasion that you actually do want to both write a new-line and flush the stream, I think it's better to do that explicitly:

std::cout << "\n" << std::flush;

At least in my experience, actual uses for this are fairly rare though.

Prefer enum's to magic numbers

Your Print currently sorts out the order for the printing like this:

if (o==1)       // ...
else if (o==2) // ...
else if(o==3)  // ...

Rather than 1, 2 and 3, I'd rather use an enumeration:

enum order { PRE_ORDER, IN_ORDER, POST_ORDER };

Then Print would look something like this:

template<typename T>
void BTree<T>::Print(order o)
{
    switch (o) { 
        case PRE_ORDER:  PrintPreOrder(root);    break;
        case IN_ORDER:   PrintInOrder(root);     break;
        case POST_ORDER: PrintPostOrder(root);   break;
    }
}

At least to me, this seems considerably clearer and more readable (also note the use of a switch statement to directly express the intent of choosing one of multiple alternatives).

Don't Repeat Yourself

Right now, you have code in both Add and Find to find a node (if any) with a particular value. Oddly, the two use entirely different approaches to this problem. Rather than having two copies of code to find a node based on a key, I'd rather have one piece of code that's used from both:

Node *&find_key(T key) { 
    Node *current = root;

    for (Node *current = root; current != nullptr;) {
        if (key < current->data)
            current = current->left;
        else if (current->data < key)
            current = current->right;
        else
           break;
    }
    return current;
}

With this, we can rewrite Find to look something like:

T Find(T key) { 
    Node *pos = find_key(key);
    if (pos != nullptr)
        return pos->data;
}

Likewise, Add would look something like this:

void Add(T key) { 
    Node *&pos = find_key(key);
    if (pos == nullptr)
        pos = new Node(key);
}

Avoid Undefined Behavior

As currently defined, if you call Find for a key that isn't present in the tree, execution flows off the end of the function without returning a value, leading to undefined behavior. There are various ways to deal with this, such as a Maybe or Optional type that carries both the return value itself and an indication whether a value is actually present. Another possibility (probably not as nice, but at least it does work) is to use an approach about like the find_key shown above, returning a null pointer if a value isn't present.

Answer 2

A few pointers I see:

• const correctness

If the function doesn't change the state use const. This allows for further optimization on the part of the compiler.

• Avoid using namespace std

Avoid using namespace std as it may lead to conflicts.

• Memory Leak

There's an obvious memory leak as you are not deleting any of the created nodes in Add. Maybe, you didn't do it on purpose. But, the code isn't complete until delete and cleanup is done.

• Using blocks in if statements

I personally have faced many issues in not using blocks for single line if statements. As a best practice I would always use it.

if(ptr->left!=nullptr) {
PrintPreOrder(ptr->left);
}

• Include test cases

Please include test cases that verify all the functionality you intend to verify in the submitted code itself. Do tests on edge cases. Ex: print in order when only a single node is present.