Stack Overflow in binary tree insertion

Question

PROCEDURE CreateNode (info: CHAR): BST;
VAR   
    bst : BST;
BEGIN
    NEW(bst);
    bst^.elem := info;
    bst^.left := NIL;
    bst^.right := NIL;
    RETURN bst;  
END CreateNode;



PROCEDURE Insert (info: CHAR; VAR t: BST);
BEGIN
    IF t = NIL THEN  
         t := CreateNode(info);  
    ELSIF Compare(info, t^.elem) = greater THEN  
         Insert(info, t^.right);  
    ELSIF Compare(info, t^.elem) = less THEN  
         Insert(info, t^.left);  
END;
END Insert;

This is causing a stack overflow when done with a FOR from 1 to a very high value (20k).

It only gets to a relatively low number (~900) before the overflow.

The issue probably is the recursive call. A function call uses the stack to store register values. If recursion goes too deep, the stack is not large enough. That's the general answer. What language is this? — GolezTrol
– GolezTrol, Commented Jun 6, 2015 at 21:22

GolezTrol · Accepted Answer · 2015-06-06 22:11:01Z

Have you searched on Stack Overflow? :p Just kidding.

The issue probably is the recursive call. A function call uses the stack to store register values, which are only removed from there if the called function ends and control is returned to the calling function. For recursive calls, all those nested calls remain on the stack until recursion is broken. Eventually the stack is not large enough and you will get this error.

You should be able to fix this by eliminating the recursion with a loop. That way, you just have iterations that jump to the next node, without all the overhead of function calls.

It can be hard to do that. Sometimes recursion seems to be the obvious way and you have to do some work to fix it in a loop.

Anyway, it should have the same logic as yours, which is, traverse the tree and look for the right spot. If the new value is smaller or larger than any leaf, it is inserted as a new node, as a leaf to the parent, and it is returned in 't'. If there is already a node with the same value, that node is returned.

To eliminate too much code duplication, the snippet below introduces a new function TryCreateNode. It tests if p (either the left or right leaf of the parent node) is nil, and if so, assigns a new node to it. It returns either p (the existing leaf) or the new node as an output parameter and returns true if a new node was created. That return value is used in the main function to break the loop.

I'm not sure which Pascal dialect you're using, so I just guessed a bit. Maybe you need to treat this as pseudo-code and fix the syntax first. ;)

FUNCTION TryCreateNode(Info: CHAR; VAR p: BST; VAR t: BST): Boolean;
BEGIN
  TryCreateNode := False;
  IF p = nil THEN 
  BEGIN
    p := CreateNode(info);
    TryCreateNode := True;
  END;
  t := p;
END;

PROCEDURE Insert (info: CHAR; VAR t: BST);
BEGIN
  WHILE t <> nil DO
  BEGIN
    IF Compare(info, t^.elem) = greater THEN
      IF TryCreateNode(info, t^.right, t) THEN
        BREAK;
    IF Compare(info, t^.elem) = less THEN
      IF TryCreateNode(info, t^.left, t) THEN
        BREAK;
  END;

END Insert;

David Hoelzer · Accepted Answer · 2015-06-06 21:23:25Z

1

Seeing that this appears to be Pascal, the cause of your problem is most likely the recursion itself. It is quite likely that the version of Pascal that you are using cannot optimize this function (or won't) for tail recursion.

answered Jun 6, 2015 at 21:23

David Hoelzer

16.4k4 gold badges54 silver badges73 bronze badges

Collectives™ on Stack Overflow

Stack Overflow in binary tree insertion

2 Answers 2

Comments

Comments

Your Answer

Hot Network Questions

Collectives™ on Stack Overflow

2 Answers 2

Comments

Comments

Your Answer

Sign up or log in

Post as a guest

Related