BST structure

Question

Hello Everyone,
I was experimenting with Binary Search Tree and I encountered a problem, my program seems to get stuck in infinite loop and I cannot localize the source of the problem. (The second function is not ready obviously.)

Code below:

#include <iostream>

using namespace std;

struct node {
int key;
node *parent;
node *left;
node *right;
};

node *addElement(node *head, int new_element) {
node *elem = new node;
elem->key = new_element;
elem->left = NULL;
elem->right = NULL;

if (head == NULL) // brak elementów - nowe drzewo
return elem;

while (head) {
if (new_element < head->key) {
if (head->left)
head = head->left;
else {
head->left = elem;
elem->parent = head;
return head;
}
} else {
if (head->right)
head = head->right;
else {
head->right = elem;
elem->parent = head;
return head;
}

}
}
}

void displayPreOrder(node *head) {
cout << head;
while (head) {
if (head->left) {
head = head->left;
cout << head;
} else if (head->right) {
head = head->right;
cout << head;
}
}
}

int main() {
node *head = nullptr;
head = addElement(head, 10);
head = addElement(head, 20);
head = addElement(head, 30);
head = addElement(head, 40);
head = addElement(head, 50);
head = addElement(head, 60);
head = addElement(head, 70);
head = addElement(head, 80);
head = addElement(head, 90);
head = addElement(head, 100);
head = addElement(head, 110);
head = addElement(head, 120);
displayPreOrder(head);
return 0;
}

Answer 1

Its easier for people to read your code if you post it in the code playground.

Your displayPreOrder() gets stuck when it reaches a valid node that has no child nodes. It stays valid, but there is nowhere for it to move and no escape condition.

Answer 2

Another issue is that you're returning the wrong head.

When you add an element to the left or the right you return that new node and not the original head.