Skip to content

Instantly share code, notes, and snippets.

@AlphaDelta
Created January 3, 2016 05:27
Show Gist options
  • Star 1 You must be signed in to star a gist
  • Fork 0 You must be signed in to fork a gist
  • Save AlphaDelta/660d359a38bcd16977f7 to your computer and use it in GitHub Desktop.
Save AlphaDelta/660d359a38bcd16977f7 to your computer and use it in GitHub Desktop.
Binary tree level order traversal
using System;
using System.Collections.Generic;
class Program
{
class BinaryNode
{
public char Letter;
public BinaryNode First = null, Second = null;
}
static BinaryNode BinaryTree =
// A
// / \
// B C
// / \ \
// D E F
new BinaryNode()
{
Letter = 'A',
First = new BinaryNode()
{
Letter = 'B',
First = new BinaryNode() { Letter = 'D' },
Second = new BinaryNode() { Letter = 'E' }
},
Second = new BinaryNode()
{
Letter = 'C',
First = new BinaryNode() { Letter = 'F' }
}
};
static void Main(string[] args)
{
Write("[ ", ConsoleColor.White);
Write("Typical loop");
Write(" ]\n", ConsoleColor.White);
//Handle our own stack to prevent a StackOverflowException
//With a typical loop it would call a method such as ProcessNode(BinaryNode), which would call itself with the nodes contained within the parent node, meaning to emulate such a process we need to use a first-in last-out collection such as Stack<T>
Stack<BinaryNode> stack = new Stack<BinaryNode>();
stack.Push(BinaryTree);
BinaryNode current;
do
{
current = stack.Pop();
Write(current.Letter + " ");
if (current.Second != null) stack.Push(current.Second);
if (current.First != null) stack.Push(current.First); //First comes last because we're using a first-in last-out collection
} while (stack.Count > 0);
Write(".\n\n[ ", ConsoleColor.White);
Write("Binary tree level order traversal");
Write(" ]\n", ConsoleColor.White);
//Use a queue instead of a stack for traversal, because it is first-in first-out
Queue<BinaryNode> queue = new Queue<BinaryNode>();
queue.Enqueue(BinaryTree);
do
{
current = queue.Dequeue();
Write(current.Letter + " ");
if (current.First != null) queue.Enqueue(current.First); //First comes first
if (current.Second != null) queue.Enqueue(current.Second);
} while (queue.Count > 0);
Write(".", ConsoleColor.White);
Console.ReadKey();
}
static void Write(string str, ConsoleColor c = ConsoleColor.Gray) { Console.ForegroundColor = c; Console.Write(str); }
}
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment