Member Avatar for zith7400

I am trying to create a binary tree. Ultimately I would like a user to be able to insert how deep he or she wants the tree to be and then have my program be able to create the tree at that depth. Root = depth 1 and so on. Here is the code I have.. it doesn't seem to do the right thing. I have set my depth level at a given number for now and have decided to implement the "asking for depth level" later on as it is not as important to me as actually getting the tree to build correctly:

#include <cstdlib>
#include <iostream>


typedef struct node
{
int data;
node *lc;
node *rc;
}node;


int deep = 3;


void traverse(node *current);


using namespace std;


int main(int argc, char *argv[])
{
node *here;
traverse(here);


system("PAUSE");
return EXIT_SUCCESS;
}


void traverse(node *current)
{
deep--;


if(deep != 0)
{
current = new node;
current->data = rand();
}
else
{
deep++;
return;
}


traverse(current->lc);
traverse(current->rc);
deep++;
}

Can anyone tell me what is wrong with this? I seem to run into a road block when the "traverse" function gets called again and it looks like it is trying to create a new node overtop of one that exists... maybe i'm just reading the code wrong.. i don't know. Obviously, you can see i'm doing this recursively. Any help would be much appreciated. Thank You!

Edited by happygeek because: fixed formatting
  • 3 Contributors
  • 2 Replies
  • 301 Views
  • 18 Hours Discussion Span
  • Latest Post Latest Post by ~s.o.s~

Dani AI

Generated

— the program crashes because here is uninitialized and traverse only changes its local copy of the pointer. As pointed out, current = new node; modifies the local parameter, so the caller still has an invalid pointer; then current->lc is dereferenced before it’s initialized. Also avoid the global deep that you decrement/increment — pass depth as a parameter instead.

A simple, safe pattern is to have the builder return the new node (or take a reference-to-pointer). Example (keeps root at depth 1):

struct Node {
    int data;
    Node* lc;
    Node* rc;
    Node(int v): data(v), lc(nullptr), rc(nullptr) {}
};

Node* buildFull(int depth) {
    if (depth <= 0) return nullptr;
    Node* n = new Node(rand());
    n->lc = buildFull(depth - 1);
    n->rc = buildFull(depth - 1);
    return n;
}

void destroy(Node* n) {
    if (!n) return;
    destroy(n->lc);
    destroy(n->rc);
    delete n;
}

Call it as Node* root = buildFull(desiredDepth); and destroy(root); when done. Alternative: void buildRef(Node*& root, int depth) sets root directly — that fixes the “local pointer” problem by using a reference.

Follow-up tips: initialize pointers to nullptr, seed or prefer std::mt19937 over rand(), compile with warnings enabled (-Wall), and run under Valgrind or address sanitizer to catch uninitialized reads. For longer-lived code prefer a Tree class that encapsulates construction/destruction (or std::unique_ptr children) as suggested — it avoids manual deletes and makes ownership explicit.

Recommended Answers

All 2 Replies

Member Avatar for GloriousEremite

Any particulary reason you're writing procedural code in C++? A better approach would be to create a tree class that handles everything.

Anyways, one major problem you have is that you pass a single pointer to traverse. The pointer in traverse is local to the function, so setting current = new node; Only modifies the pointer in the function.

Have you been reading a tutorial on binary trees? If you have, I think you should re-read it, and possibly find one that is specifically object oriented.

Member Avatar for ~s.o.s~

For a full blown implementation of Binary trees in OO C++ see here:

A good way of approaching the problem will be to jot down all the details (like variables, class design, usage etc) which though may seem as a waste of time to you will definately help you in the long run. IF this kind of documentation is made, the coding just becomes mechanical.

Be a part of the DaniWeb community

We're a friendly, industry-focused community of developers, IT pros, digital marketers, and technology enthusiasts meeting, networking, learning, and sharing knowledge.