Recursive binary tree function

Question

I am trying to insert items from my array into my tree. My function works fine and creates nodes all the way down to the leaf node on the left hand side of my tree. The problem is when it is supposed to return recursively when detecting a leaf node to the higher level, it just stops building the tree completely. Here is the code:

void WLD::treeInsert(BSP_Node *tree_root, int node_number)

{

if ( tree_root == NULL ) 
    {
        tree_root = new BSP_Node();

        tree_root->node_number = node_number;
        tree_root->normalX = bsp_array[node_number].normal[0];
        tree_root->normalY = bsp_array[node_number].normal[1];
        tree_root->normalZ = bsp_array[node_number].normal[2];
        tree_root->splitdistance = bsp_array[node_number].splitdistance;;
        tree_root->region = bsp_array[node_number].region;
        tree_root->left = bsp_array[node_number].left; //because the array starts at index 0
        tree_root->right = bsp_array[node_number].right; //because the array starts at index 0
        tree_root->left_node = NULL;
        tree_root->right_node = NULL;

        errorLog.OutputSuccess("Inserting new node: %i", node_number);
        errorLog.OutputSuccess("Left node index: %i", bsp_array[node_number].left);
        errorLog.OutputSuccess("Right node index: %i", bsp_array[node_number].right);

        node_number++;

        // Check for leaf nodes
        if(tree_root->region != 0)
        {
            errorLog.OutputSuccess("This is a leaf node! Returning!");
            return;
        }
    }


    if ( tree_root->left > 0) 
    {
        //tree_root->left_node = new BSP_Node();
        errorLog.OutputSuccess("Left node not NULL, inserting it!");
        treeInsert( tree_root->left_node, tree_root->left );
    }
    else if (tree_root->right > 0)
    {
        //tree_root->right_node = new BSP_Node();
        errorLog.OutputSuccess("Right node not NULL, inserting it!");
        treeInsert( tree_root->right_node = NULL, tree_root->right );
    }

}

As you can see, when it detects a leaf node, it is supposed to return to the calling function (this function but on a level closer to the node. Does anyone have any suggestions?

tree_root->left > 0 should probably be written tree_root->left != NULL (it just makes it clearer). — Jeff Foster
– Jeff Foster, Commented May 31, 2011 at 9:06

Jeff Foster · Accepted Answer · 2011-05-31 09:07:20Z

2

if ( tree_root->left > 0)  {
   // implementation
}
else if (tree_root->right > 0) {
   // implementation
}

Shouldn't this be two separate if statements, rather than if/else? Otherwise it only does one or the other sides, but not both.

answered May 31, 2011 at 9:07

Jeff Foster

44.9k11 gold badges90 silver badges106 bronze badges

Sign up to request clarification or add additional context in comments.

1 Comment

Dan Wilbur Over a year ago

Thank you. That was exactly the answer!

Collectives™ on Stack Overflow

Recursive binary tree function

1 Answer 1

1 Comment

Your Answer

Hot Network Questions

Collectives™ on Stack Overflow

1 Answer 1

1 Comment

Your Answer

Sign up or log in

Post as a guest

Related