Segmentation fault in a Binary Tree

Question

Either I've been staring at this code for way too long or I just can't figure this one out. but when I use an 8000 number text file in descending order; 8000, 7999, ... I get a segmentation fault in the height function. If someone could take a look I would be so greatful. Thanks.

    int BST::height(TreeNode* node)
    {

        int leftSubtree = 0;
        int rightSubtree = 0;
        if (node == NULL)
            return 0;
        else 
        {

            if (node -> getLeft() != NULL)
                leftSubtree = height(node -> getLeft());
            if(node -> getRight() != NULL)      
                rightSubtree = height(node -> getRight());

            if (leftSubtree > rightSubtree)
                return leftSubtree + 1;
            else 
                return rightSubtree + 1;
        }
    }//ends second height

That is nearly 500 lines of code. What have you been able to learn from using your debugger? Do you have a call stack to see what happens when the segfault occurs? Do you know what exactly happens to cause the segfault? Are you dereferencing a null pointer or recursing too deep? Stack Overflow is not a debugging service. — James McNellis
– James McNellis, Commented Apr 17, 2011 at 3:12
first of all, i know that its not a debugging site. I think what happens is that the left subtree recurses too far but I'm not sure why and im not sure where it happens — tpar44
– tpar44, Commented Apr 17, 2011 at 19:33

Larry Watanabe · Accepted Answer · 2011-04-17 04:39:14Z

1

If you have a sorted list of numbers then you might be storing this in a list (worst case for a tree is O(n) unless it is balanced).

In this case, your recursive routine will be recursing 8000 times with a stack depth of 8000.

I don't know if this is enough to overflow the stack, but in any case you should take a look at your tree at intermediate stages to see if everything is going down the leftmost branch.

answered Apr 17, 2011 at 4:39

Larry Watanabe

10.2k9 gold badges45 silver badges48 bronze badges

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

1 Comment

tpar44 Over a year ago

Yea i think youre right. However, that was the point, to make it all go down the left side of the tree and simulate the worst case running time of the algorithm. I forgot that the stack probably couldn't handle it so I went with a different direction.

Collectives™ on Stack Overflow

Segmentation fault in a Binary Tree

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