Math.Max Stack Overflow

[Benderbrau]

Hi guys, I've searched this, but can't find a solution. Basically what I'm doing is writing a binary search tree (which works) and balancing it with AVL (which almost works). As far as I can tell my AVL tree is implemented correctly, but I'm getting a stack overflow error at this part:

private int GetHeight(Node<T> node)
		{
			if (node!=null)
			{
				return (1+Math.Max(GetHeight(node.LeftChild), GetHeight(node.RightChild)));
			}
			else return 0;
		}

I'm using this to get the height of the tree, which I later use to calculate the tree's balance factor. I develop on Linux, but I tested this code in Windows just to be sure it wasn't an issue with MonoDevelop.

I'm retrieving this value in a method by doing

return (GetHeight(node.RightChild) - GetHeight(node.LeftChild));

Any idea what's causing this problem?

[sknake]

What are the values of the statement when you get the stack overflow message? Is this a recursion issue? Post the code for your entire class.

[Geekitygeek]

What are the values of the statement when you get the stack overflow message? Is this a recursion issue? Post the code for your entire class.

The logic looks sound to me, how deep is the tree that you are checking? As sknake said, it looks likely to be a recursion issue, but we'd need to see your code to be sure :)

[Benderbrau]

My tree isn't large at all...I'm just inserting about 30 nodes. You can probably ignore anything from Delete() and below.

This is my Binary Tree class. Insert() is used to insert nodes into a non-balanced binary search tree. Insert2() is the same, except at the end I call Rebalance() with the previous node passed through.

using System;
using System.Collections.Generic;

namespace BinaryTreeLib
{
	
	
	public class BinaryTree<T> : IBinaryTree<T> where T: IComparable
	{
		private Node<T> root; //keep track of the root
		private Node<T> _root; //used later

		public void Insert(T nodeValue) //used to insert Node in non-blanaced binary search tree
		{
			Console.WriteLine("***Adding "+nodeValue+" to tree...");
			if (root == null)
            {
				Console.WriteLine("Tree is empty, so let's make a root...");
                root = new Node<T>(nodeValue);
				Console.WriteLine("Root is "+root.Value);
            }
			else
			{
				Node<T> currentNode = root;
                Node<T> previousNode = root;

                while (currentNode != null)
                {
                    if (currentNode.CompareTo(nodeValue) < 0)
                    {//if current node is less, then goto next node (previous = current, current = previous's left child)
                        previousNode = currentNode;
						currentNode = previousNode.LeftChild;
						//LeftChild.Insert(newNode);
                    }
                    else if (currentNode.CompareTo(nodeValue) > 0)
                    {//if current node is greater, then goto next node (previous = current, current = previous's right child)
                        previousNode = currentNode;
						currentNode = previousNode.RightChild;
					//	Console.WriteLine(nodeValue+" is greater than "+previousNode.Value+"...");
                    }
                }

				
				//update the node's parents
                if (previousNode.CompareTo(nodeValue) < 0)
                {
					Console.WriteLine(nodeValue+" is a left child of "+previousNode.Value);
                    previousNode.LeftChild = new Node<T>(nodeValue, previousNode);
                }
                else
                {
					Console.WriteLine(nodeValue+" is a right child of "+previousNode.Value);
                    previousNode.RightChild = new Node<T>(nodeValue, previousNode);
                }

			}
		}
		public void Insert2(T nodeValue) //used to insert nodes in AVL balanced tree
		{
			Node<T> newNode = new Node<T>(nodeValue);
			Console.WriteLine("***Adding "+nodeValue+" to tree...");
			if (root == null)
            {
				Console.WriteLine("Tree is empty, so let's make a root...");
                root = newNode;//new Node<T>(nodeValue);
				Console.WriteLine("Root is "+root.Value);
            }
			else
			{
				Node<T> currentNode = root; //used to traverse through each node
                Node<T> previousNode = root; //used to store the last used node

                while (currentNode != null)
                {
                    if (currentNode.CompareTo(nodeValue) < 0)
                    {//if current node is less, then goto next node (previous = current, current = previous's left child)
                        previousNode = currentNode;
						currentNode = previousNode.LeftChild;
						//LeftChild.Insert(newNode);
                    }
                    else if (currentNode.CompareTo(nodeValue) > 0)
                    {//if current node is greater, then goto next node (previous = current, current = previous's right child)
                        previousNode = currentNode;
						currentNode = previousNode.RightChild;
                    }
                }

				
				//update node's parents
                if (previousNode.CompareTo(nodeValue) < 0)
                {
					//Console.WriteLine(nodeValue+" is a left child of "+previousNode.Value);
                    previousNode.LeftChild = new Node<T>(nodeValue, previousNode);
                }
                else
                {
					//Console.WriteLine(nodeValue+" is a right child of "+previousNode.Value);
                    previousNode.RightChild = new Node<T>(nodeValue, previousNode);
             }
				ReBalance(previousNode);
			}
		}
		private void ReBalance(Node<T> node)
		{
			Node<T> parent = node.Parent;
			while (parent != null)
			{
				int balance = GetBalance(parent);
				if (Math.Abs(balance) == 2)
				{
					BalanceAt(parent, balance);
				}
				parent = parent.Parent;
			}
		}
		private void BalanceAt(Node<T> node, int balance)
		{
			if (balance == 2) //if balance factor is 2, then tree is unbalanced
			{
				int rightBalance = GetBalance(node.RightChild);
				if (rightBalance == 1 || rightBalance == 0)
				{
					RotateLeft(node);
				}
				else if (rightBalance == -1)
				{
					Console.WriteLine("Performing Complex R-L rotation at node " +node.Value);
					RotateRight(node.RightChild);
					RotateLeft(node);
				}
			}
		else if (balance == -2) //if balance factor is -2, then tree is unbalanced
			{
				int leftBalance = GetBalance(node.LeftChild);
				if (leftBalance == -1 || leftBalance == 0)
				{
					RotateRight(node);
				}
				else if (leftBalance == 1)
				{
					Console.WriteLine("Performing complex L-R Rotation at node " + node.Value);
					RotateLeft(node.LeftChild);
					RotateRight(node);
				}
			}
		}
		private int GetHeight(Node<T> node)
		{
			if (node!=null)
			{
				return (1+Math.Max(GetHeight(node.LeftChild), GetHeight(node.RightChild)));
			}
			else return 0;
		}
		private int GetBalance(Node<T> node)
		{
			if (node != null)
			{
				return (GetHeight(node.RightChild) - GetHeight(node.LeftChild));
			}
			else return 0;
		}
		private void RotateLeft(Node<T> node)
		{
			if (node == null)
			{
				return;
			}
			Node<T> pivot = node.RightChild;
			if (pivot == null)
			{
				return;
			}
			else
			{
				Console.WriteLine("Performing Basic Left Rotation at node " + node.Value);
				Node<T> nodesParent = node.Parent;
				bool isLeftChild  = (nodesParent != null) && nodesParent.LeftChild == node;
				bool makeTreeRoot = (_root == node);
				node.RightChild = pivot.LeftChild;
				pivot.LeftChild = node;
				node.Parent = pivot;
				pivot.Parent = nodesParent;
				if (node.RightChild != null)
				{
					node.RightChild.Parent = node;
				}
				if (makeTreeRoot)
				{
					_root = pivot;
				}
				if (isLeftChild)
				{
					nodesParent.LeftChild = pivot;
				}
				else
				{
					if (nodesParent != null)
					{
						nodesParent.RightChild = pivot;
					}
				}
			}
		}
		private void RotateRight(Node<T> node)
		{
			if (node == null)
			{
				return;
			}
			Node<T> pivot = node.LeftChild;
			if (pivot==null)
			{
				return;
			}
			else
			{
				Console.WriteLine("Performing Basic Right Rotation at node " + node.Value);
				Node<T> nodesParent = node.Parent;
				bool isLeftChild = (nodesParent != null) && nodesParent.LeftChild == node;
				bool makeTreeRoot = (_root == node);
				root.LeftChild = pivot.RightChild;
				pivot.RightChild = node;
				node.Parent = pivot;
				pivot.Parent = nodesParent;
				if (node.LeftChild != null)
				{
					node.LeftChild.Parent = node;
				}
				if (makeTreeRoot)
				{
					_root = pivot;
				}
				if (isLeftChild)
				{
					nodesParent.LeftChild = pivot;
				}
				else
				{
					if (nodesParent != null)
					{
						nodesParent.RightChild = pivot;
					}
				}
			}
			
		}
		public void Delete(T nodeValue)
		{
		}
		/// <summary>
		/// START PREORDER
		/// </summary>
		public void Preorder()
		{
			PreorderTraverse(root);
		}
		private void PreorderTraverse(Node<T> node)
		{
			if (node == null)
				return;
			Console.WriteLine(node.Value);
			PreorderTraverse(node.LeftChild);
			PreorderTraverse(node.RightChild);
		}
		
		/// <summary>
		/// START INORDER
		/// </summary>
		public void Inorder()
		{
			InorderTraversal(root);
		}
		private void InorderTraversal(Node<T> node)
		{
			if (node == null)
				return;
			InorderTraversal(node.LeftChild);
			Console.WriteLine(node.Value);
			InorderTraversal(node.RightChild);
		}
		
		/// <summary>
		/// START POSTORDER
		/// </summary>
		public void Postorder()
		{
			PostorderTraversal(root);
		}
		private void PostorderTraversal(Node<T> node)
		{
			if (node == null)
				return;
			PostorderTraversal(node.LeftChild);
			PostorderTraversal(node.RightChild);
			Console.WriteLine(node.Value);
		}
		
		
		public void MakeNull()
		{ //just deleting the root for now...eventually will delete from leaf nodes up
			if (root != null)
			{
				//PostOrderDelete(root);
				root = null;
			}
		}
		private void PostOrderACE(Node<T> node, int currentLevel, List<int> levelCounts)
		{
			if (node.LeftChild != null)
			{
				PostOrderACE(node.LeftChild, currentLevel + 1, levelCounts);
			}
			if (node.RightChild != null)
			{
				PostOrderACE(node.RightChild, currentLevel +1, levelCounts);
			}
			levelCounts.Add(currentLevel);
		}
		public float ACE
		{
			get
			{
				if (root != null)
				{
					List<int> levelCounts = new List<int>();
					PostOrderACE(root, 1, levelCounts);
					
					float total = 0.0F;
					float nodeCount = (float)levelCounts.Count;
					foreach (int i in levelCounts)
					{
						total += (float)i;
					}
					return total / nodeCount;
				}
				else return 0.0F;
			}
		}
	}
}

And then to insert the nodes, I use these lines in my main class...

int[] NodeValueList = {8,22,14,35,43,56,82,19,17,27,54,89,75,29,16,21,23,24,25,26,55,36,49,20,1,9,11,86,5,50};
			IBinaryTree<int> Tree = new BinaryTree<int>();
foreach (int numbers in NodeValueList)
			{
				Tree.Insert2(numbers);
			}

My Node<T> class that is called is simply used to keep track of the node properties, such as Parent, Left and Right Child, and Value.

[Geekitygeek]

Have you tried stepping through the recursion to see what point the stack overflow occurs? I'm afraid i'm not overly familiar with debugging the call stack so someone else might offer a better way to find your problem, but looking at your code it would seem that the problem is in the recursive calls to GetHeight().
When the parent is the root node then the number of calls in the stack is equal to the total number of nodes. How many calls it takes to overflow the stack depends on the size of your stack and the size of the passed object. How big is a single node object and how big is your stack?

[Benderbrau]

Ah, got it! Thanks for the help everyone, it was a silly mistake. In line #222 i had

root.LeftChild = pivot.RightChild;

I replaced root with node and everything's working fine! Whew! Sorry for the wasted time, it seems like I spend hours on silly errors like these! At least I know more about what causes a stack overflow now, ha.

[Geekitygeek]

Ah, got it! Thanks for the help everyone, it was a silly mistake. In line #222 i had

root.LeftChild = pivot.RightChild;

I replaced root with node and everything's working fine! Whew! Sorry for the wasted time, it seems like I spend hours on silly errors like these! At least I know more about what causes a stack overflow now, ha.

That is so often the way :p Glad you got this one under control. Remember to mark the thread as solved.

[Rashakil Fol]

Remember to mark the thread as solved.

Who cares?

[Geekitygeek]

Who cares?

Firstly, me...secondly, a fair few of the solvers i've seen here on the boards. Marking a thread as solved indicates to others that the problem no longer requries attention, and a reminder to mark seems to be a very common closing comment.

You're hardly new to the boards, why make such an inane comment?

[Rashakil Fol]

Firstly, me...secondly, a fair few of the solvers i've seen here on the boards.

Really, you and other people? Who would have thought?

Marking a thread as solved indicates to others that the problem no longer requries attention,

No, it indicates that people think it no longer requires attention, but adds a presumption of the correctness of the answer -- and frequently a thread's OP isn't qualified to judge that matter.

and a reminder to mark seems to be a very common closing comment.

So?

[sknake]

Really, you and other people? Who would have thought?

No, it indicates that people think it no longer requires attention, but adds a presumption of the correctness of the answer -- and frequently a thread's OP isn't qualified to judge that matter.

So?

Rashakil,

Why do you even bother talking? Half of the time you aren't contributing anyways. The OP is the only person qualified to answer the question of "did the solution work for me?" They are seeking answers to their problems. We're not solving world development problems here.

Please do us a favor and contribute or shut up.

Oh -- and did this solution work for the OP? Or are you not qualified to answer?

[Geekitygeek]

The OP is the only person qualified to answer the question of "did the solution work for me?" They are seeking answers to their problems. We're not solving world development problems here.

Exactly, if the OP is satisfied that the problem has been resolved then there is no need for solvers to continue contributing to the thread. Marking the thread as solved means they can see from the forum page that the OP no longer needs help.

Only the OP can decide when they no longer need assistance, but many join the boards to post their problem so they aren't aware of the system. Others simply forget to mark. A casual reminder ensures solvers can spend their time reading threads that still require their input.

As a solver and former moderator yourself you must surely know all this.

[Ancient Dragon]

Exactly, if the OP is satisfied that the problem has been resolved then there is no need for solvers to continue contributing to the thread. Marking the thread as solved means they can see from the forum page that the OP no longer needs help.

Although technically you are correct, sometimes it doesn't work like that. I've seen discussions continue even after the thread has been marked solved. And there is no rule to prevent it, for good reason. The op may be satisfied with the result but other contributors may want further discussions.

[Geekitygeek]

Although technically you are correct, sometimes it doesn't work like that. I've seen discussions continue even after the thread has been marked solved. And there is no rule to prevent it, for good reason. The op may be satisfied with the result but other contributors may want further discussions.

I totally agree, and theres nothing preventing them from doing so...this discussion being a perfect example :) Once the thread is marked as solved the posters are free to continue any discussions/contributions.
However, if you have not previously visited the thread, you can see from the solved: tag in the forum listing that it doesnt require any further input. If you feel like reading through and throwing in your thoughts you can.
I personally would much rather spend my time reading and contributing to threads that still require a solution before i go back and add to solved threads. If the OP is satisfied but hasnt marked the post then there are sometimes several pages of posts to read through only to find out it no longer needs any input :p

[Rashakil Fol]

Please do us a favor and contribute or shut up.

Why do you get so butthurt when you see people with different worldviews than yours?

[sknake]

Why do you get so butthurt when you see people with different worldviews than yours?

I don't get "butthurt". I just get tired of watching you post and complaining about what other people say, -rep them, down vote them, and generally antagonize people because you want to be an ass that day all the while you're contributing little. If you want to post just to talk then take it out of the programming forums and head over to the Geek's lounge or fire up notepad so I don't have to read what you say. I'm not seeing anyone rushing to your defense here so maybe other people share the same view.

[Rashakil Fol]

4I just get tired of watching you post and complaining about what other people say, -rep them, down vote them, and generally antagonize people because you want to be an ass that day all the while you're contributing little.

I just don't want people to mark threads solved.

[Geekitygeek]

I just don't want people to mark threads solved.

Why not? Thats what really astounds me...theres a reason the system exists, why on earth do you want people not to use it?
And does it affect you so profoundly that you feel you have to stop people from using it?
It doesnt stop people viewing the thread, or posting in it, so if you want to ignore the sovled status, go ahead.

[Rashakil Fol]

The reason it exists is because somebody put it there. Supporting the marking of threads as solved is like supporting the death penalty: innocent people will get executed, and threads with bad solutions will marked as solved.

[Geekitygeek]

But only the OP can mark the thread as solved. If they are satisfied that the problem is resolved and they have a working solution (be it a good or a bad one) then chances are they aren't going to come back to check the thread anymore anyway (marked or otherwise).
You are right in the fact that, just because it is marked solved, it doesnt mean the best possible solution has been provided. But the solved tag does provide an indicator as to whether the OP is still waiting for a solution. Again, just because its marked as solve, doesnt stop you posting your views/solutions. What it does do, is allow solvers to spend time responding to questons which (in the eys of the OP) still need attention.

[Rashakil Fol]

The real value of a forum like Daniweb is in how it helps the people who search for problems in the future. The needs of the OP are immaterial.

[Geekitygeek]

The needs of the OP are immaterial.

Seriously?? If their needs dont matter then why bother posting at all?

The real value of a forum like Daniweb is in how it helps the people who search for problems in the future.

I only wish that were so :p I've lost count of how many times i've seen "How do i make a login form" in the C# forum. There are countless answered threads and at least one code snippet guide that i know of.

I see where your coming from, and i agree to an extent. If the OP gets a bad solution then marks the thread as solved, if noone goes in to correct it (because it says solved), someone may search for an answer and find the bad one. That's undesirable, admittedly, but as i said, there is nothing to stop you checking in on solved threads and adding a better solution for those who come to it later. I often read through a solved thread to see how it resolved. My point is, i dont have enough time in the day to read the entirety of every single thread. If the OP is happy then a workable solution has been found (be it good or bad) so i can skip it for now. I can spend my time reading through and contributing to threads which still require immediate help for the OP. Then, if time allows, i can go back to solved threads to see if theres any more to be said. I knwo i dont speak for everyone, and i wouldnt pressume to.
But personally, i think the 'Mark as Solved' feature is very useful and will continue to advise the posters i help to mark the thread when they are happy.
If you or others dont like the system, then ignore it. There is nothing there to enforce it; a solved thread doesnt prevent you from posting in it.