How to avoid this stackoverflow exception?

Question

Here is the situation, I am developing a binary search tree and in each node of the tree I intend to store the height of its own for further balancing the tree during avl tree formation. Previously I had an iterative approach to calculate the height of a node during balancing the tree like the following.

(The following code belongs to a class called AVLTree<T> which is a child class of BinarySearchTree<T>)

protected virtual int GetBalance(BinaryTreeNode<T> node)
        {
            if(node != null)
            {
                IEnumerable<BinaryTreeNode<T>> leftSubtree = null, righSubtree = null;

                if (node.Left != null)
                    leftSubtree = node.Left.ToEnumerable(BinaryTreeTraversalType.InOrder);

                if (node.Right != null)
                    righSubtree = node.Right.ToEnumerable(BinaryTreeTraversalType.InOrder);


                var leftHeight = leftSubtree.IsNullOrEmpty() ? 0 : leftSubtree.Max(x => x.Depth) - node.Depth;
                var righHeight = righSubtree.IsNullOrEmpty() ? 0 : righSubtree.Max(x => x.Depth) - node.Depth;


                return righHeight - leftHeight;
            }
            return 0;            
        }

But it was incurring a lot of performance overhead.

http://stackoverflow.com/questions/3668365/performance-of-an-avl-tree-in-c

So I went for storing the height value in each node at the time of insertion in the BinarySearchTree<T>. Now during balancing I am able to avoid this iteration and I am gaining the desired performance in AVLTree<T>.

But now the problem is if I try to insert a large number of data say 1-50000 sequentially in BinarySearchTree<T> (without balancing it), I am getting StackoverflowException. I am providing the code which is causing it. Can you please help me to find a solution which will avoid this exception and also not compromise with the performance in its child class AVLTree<T>?

public class BinaryTreeNode<T>
    {
        private BinaryTreeNode<T> _left, _right;
        private int _height;

        public T Value {get; set; }
        public BinaryTreeNode<T> Parent;
        public int Depth {get; set; }

        public BinaryTreeNode()
        {}

        public BinaryTreeNode(T data)
        {
            Value = data;
        }

        public BinaryTreeNode<T> Left
        {
            get { return _left; }
            set
            {
                _left = value;
                if (_left != null)
                {
                    _left.Depth = Depth + 1;    
                    _left.Parent = this;
                }                
                UpdateHeight();
            }
        }

        public BinaryTreeNode<T> Right
        {
            get { return _right; }
            set
            {
                _right = value;
                if (_right != null)
                {
                    _right.Depth = Depth + 1;
                    _right.Parent = this;
                }
                UpdateHeight();
            }
        }

        public int Height
        {
            get { return _height; }
            protected internal set
            {
                _height = value;
                if (Parent != null) {
                    Parent.UpdateHeight();
                }               
            }
        }

        private void UpdateHeight()
        {
            if (Left == null && Right == null) {
                return;
            }
            if(Left != null && Right != null)
            {
                if (Left.Height > Right.Height)
                    Height = Left.Height + 1;
                else
                    Height = Right.Height + 1;
            }
            else if(Left == null)
                Height = Right.Height + 1;
            else
                Height = Left.Height + 1;
        }

    }

---

public class BinarySearchTree<T>
    {
        private readonly Comparer<T> _comparer = Comparer<T>.Default;

        public BinarySearchTree()
        {
        }

        public BinaryTreeNode<T> Root {get; set;}

        public virtual void Add(T value)
        {
            var n = new BinaryTreeNode<T>(value);
            int result;

            BinaryTreeNode<T> current = Root, parent = null;
            while (current != null)
            {
                result = _comparer.Compare(current.Value, value);
                if (result == 0)
                {
                    parent = current;
                    current = current.Left;
                }
                if (result > 0)
                {
                    parent = current;
                    current = current.Left;
                }
                else if (result < 0)
                {
                    parent = current;
                    current = current.Right;
                }
            }

            if (parent == null)
                Root = n;
            else
            {
                result = _comparer.Compare(parent.Value, value);
                if (result > 0)
                    parent.Left = n;
                else
                    parent.Right = n;
            }
        }
    }

I am getting the StackoverflowException in calculating the height at the following line

if (Parent != null) {
                    Parent.UpdateHeight();
                } 

in the Height property of BinaryTreeNode<T> class. If possible please suggest me some work around.

BTW, thanks a lot for your attention to read such a long question :)

Answer 1

When you add a node you compute the height by iterating over all the parent nodes recursively. A .NET process has limited stack space and given a big tree you will consume all stack space and get a StackOverflowException. You can change the recursion into an iteration to avoid consuming stack space. Other languages like functional languages are able to recurse without consuming stack space by using a technique called tail recursion. However, in C# you will have to manually modify your code.

Here are modified versions of Height and UpdateHeight in BinaryTreeNode<T> that doesn't use recursion:

public int Height {
  get { return _height; }
  private set { _height = value; }
}

void UpdateHeight() {
  var leftHeight = Left != null ? Left.Height + 1 : 0;
  var rightHeight = Right != null ? Right.Height + 1 : 0;
  var height = Math.Max(leftHeight, rightHeight);
  var node = this;
  while (node != null) {
    node.Height = height;
    height += 1;
    node = node.Parent;
  }
}

Answer 2

You can add a tail. call in il, decompile the file and then compile it again.

Example:

.... IL_0002: add

tail.

IL_0003: call ...

IL_0008: ret

Example on compiling it again:

ilasm C:\test.il /out=C:\TestTail.exe

(this is probably not what you want, but again it's just an example)

I'm sure you can figure it out and make it work, it's not to hard.

The big downside is that recompilation will get rid of your tail call so I recommend to set up a build task in msbuild to do it automatically for you.

Answer 3

I think I found the solution, I modified the code as follows and it worked like a charm

public int Height
        {
            get { return _height; }
            protected internal set
            {
                _height = value;                                
            }
        }

        private void UpdateHeight()
        {
            if (Left == null && Right == null) {
                return;
            }
            if(Left != null && Right != null)
            {
                if (Left.Height > Right.Height)
                    Height = Left.Height + 1;
                else
                    Height = Right.Height + 1;
            }
            else if(Left == null)
                Height = Right.Height + 1;
            else
                Height = Left.Height + 1;

            var parent = Parent;
            while (parent != null) {
                parent.Height++;
                parent = parent.Parent;             
            }           

        }

Thanks a lot guys who spend some time for me to tried to find out the solution.

Answer 4

If you are inserting large amounts of data in one go I would think you'd be better of batch inserting the data without the call to Parent.UpdateHeight then walk the tree setting the height as you go.

Adding future nodes I would walk the tree, starting at the root, incrementing the height as you go.