Iterative Binary Search Tree C++; Why sometimes my program run correctly and other time not?

Question

I am trying to insert new nodes to binary search tree. I get no error, but if I run this program sometimes the tree displays correctly in cmd and sometimes nothing happens and the program doesn't crash, but the console is like waiting for something. I can't figure it out where the mistake is. Here is the code:

#include <iostream>
#include <string>

template <typename T>
class BinarySearchTree {
public:

    class Node {
    public:
        T data;
        Node* left;
        Node* right;
    };

    Node* root;
    BinarySearchTree() {
        root = nullptr;
    }

    Node* getRoot() {
        return root;
    }

    Node* createNode(T data) {
        Node* newNode = new Node();
        newNode->data = data;
        newNode->left = nullptr;
        newNode->right = nullptr;
        return newNode;
    }

    Node* insert(Node*& root, T data) {
        Node* current = root;
        Node* prev = nullptr;

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

        if (prev == nullptr)
            prev = createNode(data);
        else if (prev->data < data)
            prev->right = createNode(data);
        else if (prev->data > data)
            prev->left = createNode(data);
        else if (prev->data == data)
            prev->data = data;
        return prev;
    }

    class Trunk {
    public:
        Trunk* prev;
        std::string str;

        Trunk(Trunk* prev, std::string str) {
            this->prev = prev;
            this->str = str;
        }
    };

    void showTrunks(Trunk* p) {
        if (p == nullptr)
            return;

        showTrunks(p->prev);
        std::cout << p->str;
    }

    void printTree(Node* root, Trunk* prev, bool isLeft) {
        if (root == nullptr)
            return;

        std::string prev_str = "    ";
        Trunk* trunk = new Trunk(prev, prev_str);

        printTree(root->right, trunk, true);

        if (!prev)
            trunk->str = "---";
        else if (isLeft) {
            trunk->str = ".---";
            prev_str = "   |";
        }
        else {
            trunk->str = "`---";
            prev->str = prev_str;
        }

        showTrunks(trunk);
        std::cout << " " << root->data << std::endl;

        if (prev)
            prev->str = prev_str;

        trunk->str = "   |";

        printTree(root->left, trunk, false);
    }
};

struct Point {
    int x;
    int y;

    Point(int x, int y) {
        this->x = x;
        this->y = y;
    }

    Point() {
        x = 0;
        y = 0;
    }

    bool operator>(const Point& point) {
        if ((x + y) > (point.x + point.y))
            return true;
        return false;
    }

    bool operator<(const Point& point) {
        if ((x + y) < (point.x + point.y))
            return true;
        return false;
    }

    bool operator==(const Point& point) {
        if ((x + y) == (point.x + point.y))
            return true;
        return false;
    }

    bool operator!=(const Point& point) {
        if ((x + y) != (point.x + point.y))
            return true;
        return false;
    }
};

std::ostream& operator<<(std::ostream& COUT, Point& point) {
    COUT << "(" << point.x << ", " << point.y << ")";
    return COUT;
}

And here is the main function:


int main()
{
    srand(time(0));
    BinarySearchTree<Point>* tree = new BinarySearchTree<Point>();
    BinarySearchTree<Point>::Node* root = tree->getRoot();

    Point point;
    point.x = 100;
    point.y = 100;
    root = tree->insert(root, point);
    for (int i = 0; i < 10; i++) {
        Point point;
        point.x = rand() % 100;
        point.y = rand() % 100;
        tree->insert(root, point);
    }
    tree->printTree(root, nullptr, false);

    return 0;
}

It sounds like you may need to learn how to use a debugger to step through your code. With a good debugger, you can execute your program line by line and see where it is deviating from what you expect. This is an essential tool if you are going to do any programming. Further reading: [How to debug small programs](http://ericlippert.com/2014/03/05/how-to-debug-small-programs/) and [Debugging Guide](http://idownvotedbecau.se/nodebugging/) — NathanOliver, Oct 26 '22 at 19:51
Why are you doing a dynamic allocation for `tree` in `BinarySearchTree* tree = new BinarySearchTree();` ? You leak that memory. Also `tree->getRoot();` returns `root` which is uninitialized — Ted Lyngmo, Oct 26 '22 at 19:56
Debugging with random numbers is more trouble than it's worth. Split `srand(time(0));` into two parts `time_t seed = time(nullptr);` and `srand(seed);` and print out seed every time. When you find a case that does not work, replace the call to `time` with the time that caused the failure. This will allow you to run the same random sequence over and over until you spot the problem. And then you can make the changes and verify they really did fix the problem (and not introduce new ones). — user4581301, Oct 26 '22 at 19:58
[What is a debugger and how can it help me diagnose problems?](https://stackoverflow.com/questions/25385173/what-is-a-debugger-and-how-can-it-help-me-diagnose-problems) — Jesper Juhl, Oct 26 '22 at 20:58
This doesn't address the question, but the first half of the code in `insert` should be in a separate function named `find`. — Pete Becker, Oct 26 '22 at 21:28

score -1 · Accepted Answer · answered Oct 26 '22 at 19:56

During

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

If current->data is equal to data, what will happen? You will continue the loop, with current unchanged. This will loop forever. That would explain your program hanging.

There is also no point in passing a reference in:

Node* insert(Node*& root, T data)

This would do just as well an be less of an eye sore:

Node* insert(Node* root, T data)

Iterative Binary Search Tree C++; Why sometimes my program run correctly and other time not?

1 Answers1