Skip to content

Instantly share code, notes, and snippets.

@DeepSky8
Last active February 25, 2016 19:47
Show Gist options
  • Save DeepSky8/147bcd0955ebe368685f to your computer and use it in GitHub Desktop.
Save DeepSky8/147bcd0955ebe368685f to your computer and use it in GitHub Desktop.
BreadthTraverse gets stuck somewhere. When I use the debug feature, Visual Studio hits an error and closes after line 173.
using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;
using System.Threading.Tasks;
namespace BinaryTree
{
class Program
{
static void Main(string[] args)
{
var newBST = new BSTNode<int>();
newBST.Add(12);
newBST.Add(6);
newBST.Add(18);
newBST.Add(3);
newBST.Add(14);
newBST.Add(9);
newBST.Add(17);
Console.WriteLine(newBST.TraverseBST());
}
}
public class BSTNode<T> where T : IComparable<T>
{
public T Value { get; set; }
public BSTNode<T> Right { get; protected set; }
public BSTNode<T> Left { get; protected set; }
public bool Unprinted { get; protected set; } = true;
public int Count { get; protected set; } = 0;
public void Add(T newValue)
{
var newNode = new BSTNode<T>();
//If this node does not hold a value, set it to the value currently being added. If the node equals 0, increment the Count at this node.
if (Value == null || Value.Equals(0))
{
if (Value.Equals(newValue))
{
Count += 1;
}
Value = newValue;
}
//If there is a value in the node, or the base node value is not 0, compare the new value to the current node value.
//Either increment the count by 1, or determine if child node [left or right] exists.
//Call Add with the newValue on the (possibly newly created) [left or right] node.
else
{
switch (Value.CompareTo(newValue))
{
case 0:
Count += 1;
break;
case -1:
if (Left == null)
{
Left = newNode;
}
Left.Add(newValue);
break;
case 1:
if (Right == null)
{
Right = newNode;
}
Right.Add(newValue);
break;
default:
break;
}
}
}
public string TraverseBST()
{
var addToString = new StringBuilder();
//Check if left node exists to determine if on leaf or node
//If a left child exists, confirm that it has not been printed
if (Left != null && Left.Unprinted)
{
//call TraverseBST on the left child, and put the information at the beginning of the string builder
addToString.Insert(0, (Left.TraverseBST()+","), 1);
}
else
{
if (Unprinted)
{
var localStringArray = new T[Count];
for (int i = 0; i < Count; i++)
{
localStringArray[i] = Value;
}
addToString.Append(string.Join(",", localStringArray));
Unprinted = false;
}
}
//Check if right node exists to determine if on leaf or node
//If a right child exists, confirm that it has not been printed
if (Right != null && Right.Unprinted)
{
//call TraverseBST on the right child, and put the information at the end of the string builder
addToString.Append(Right.TraverseBST());
Right.Unprinted = false;
}
//else
//{
// if (Unprinted)
// {
// var localStringArray = new T[Count];
// for (int i = 0; i < Count; i++)
// {
// localStringArray[i] = Value;
// }
// addToString.Append(string.Join(",", localStringArray));
// Unprinted = false;
// }
//}
return addToString.ToString();
}
}
}
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment