Binary Tree Breath-first vs Depth-first Traversal

BinaryTreeTraversal.cs

using System;
using System.Linq;
using System.Collections.Generic;

public class Program
{
	public static void Main()
	{
		BTTraversal();
	}
	
	//                 1
	//         2              3
	//     4      5        6      7
	//   8   9  10  11  12  13  14  15
	private static void BTTraversal(){
		var n1 = new BTNode<int>(1);
		var n2 = new BTNode<int>(2);
		var n3 = new BTNode<int>(3);
		var n4 = new BTNode<int>(4);
		var n5 = new BTNode<int>(5);
		var n6 = new BTNode<int>(6);
		var n7 = new BTNode<int>(7);
		var n8 = new BTNode<int>(8);
		var n9 = new BTNode<int>(9);
		var n10 = new BTNode<int>(10);
		var n11 = new BTNode<int>(11);
		var n12 = new BTNode<int>(12);
		var n13 = new BTNode<int>(13);
		var n14 = new BTNode<int>(14);
		var n15 = new BTNode<int>(15);
		
		// Build binary tree
		var root = n1;
		root.Insert(n2, n3);
		n2.Insert(n4, n5);
		n4.Insert(n8, n9);
		n5.Insert(n10, n11);
		n3.Insert(n6, n7);
		n6.Insert(n12, n13);
		n7.Insert(n14, n15);
		
		// Traverse the tree
		var traverser = new BTTraverser<int>(root);
		
		Console.WriteLine("Breath-first traversal");
		traverser.TraverseBreathFirst(node => Console.Write(node.Value + " "));
		
		Console.WriteLine("\n\nDepth-first traversal");
		traverser.TraverseDepthFirst(node => Console.Write(node.Value + " "));
	}
}

class BTTraverser<T>{
	private BTNode<T> _root;
	
	public BTTraverser(BTNode<T> root){
		_root = root;
	}
	
	public void TraverseBreathFirst(Action<BTNode<T>> action){
		var q = new Queue<BTNode<T>>();
		q.Enqueue(_root);
		while(q.Any()){
			var current = q.Dequeue();
			if (current == null)
				continue;
			action(current);
			q.Enqueue(current.Left);
			q.Enqueue(current.Right);
		}
	}
	
	public void TraverseDepthFirst(Action<BTNode<T>> action){
		var s = new Stack<BTNode<T>>();
		s.Push(_root);
		while(s.Any()){
			var current = s.Pop();
			if (current == null)
				continue;
			action(current);
			s.Push(current.Right);
			s.Push(current.Left);
		}
	}
}

class BTNode<T>
{
	public T Value { get; private set; }
	
	public BTNode<T> Left {get; set;}
	public BTNode<T> Right {get; set;}
	
	public BTNode(T value){
		Value = value;
	}
	
	public void Insert(BTNode<T> left, BTNode<T> right){
		Left = left;
		Right = right;
	}
}

/*
    Output:
    
    Breath-first traversal
    1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 

    Depth-first traversal
    1 2 4 8 9 5 10 11 3 6 12 13 7 14 15
*/

BinaryTreeTraversalUsingVisitorPattern.cs

using System;
using System.Linq;
using System.Collections.Generic;

public class Program
{
	public static void Main()
	{
		BTTraversal();
	}
	
	//                 1
	//         2              3
	//     4      5        6      7
	//   8   9  10  11  12  13  14  15
	private static void BTTraversal(){
		var n1 = new BTNode<int>(1);
		var n2 = new BTNode<int>(2);
		var n3 = new BTNode<int>(3);
		var n4 = new BTNode<int>(4);
		var n5 = new BTNode<int>(5);
		var n6 = new BTNode<int>(6);
		var n7 = new BTNode<int>(7);
		var n8 = new BTNode<int>(8);
		var n9 = new BTNode<int>(9);
		var n10 = new BTNode<int>(10);
		var n11 = new BTNode<int>(11);
		var n12 = new BTNode<int>(12);
		var n13 = new BTNode<int>(13);
		var n14 = new BTNode<int>(14);
		var n15 = new BTNode<int>(15);
		
		// Build binary tree
		var root = n1;
		root.Insert(n2, n3);
		n2.Insert(n4, n5);
		n4.Insert(n8, n9);
		n5.Insert(n10, n11);
		n3.Insert(n6, n7);
		n6.Insert(n12, n13);
		n7.Insert(n14, n15);
		
		// Traverse the tree
		var bfTraverser = new BreathFirstTraverser<int>(root, node => Console.Write(node.Value + " "));
		var dfTraverser = new DepthFirstTraverser<int>(root, node => Console.Write(node.Value + " "));
		
		Console.WriteLine("Breath-first traversal");
		root.Accept(bfTraverser);
		
		Console.WriteLine("\n\nDepth-first traversal");
		root.Accept(dfTraverser);
	}
}

abstract class BTVisitor<T>{
	protected BTNode<T> _root;
	protected Action<BTNode<T>> _action;
	
	public abstract void Visit();
	
	public BTVisitor(BTNode<T> root, Action<BTNode<T>> action){
		_root = root;
		_action = action;
	}
}

class BreathFirstTraverser<T> : BTVisitor<T>{
	public BreathFirstTraverser(BTNode<T> root, Action<BTNode<T>> action) : base(root, action){}
	
	public override void Visit(){
		var q = new Queue<BTNode<T>>();
		q.Enqueue(_root);
		while(q.Any()){
			var current = q.Dequeue();
			if (current == null)
				continue;
			_action(current);
			q.Enqueue(current.Left);
			q.Enqueue(current.Right);
		}
	}
}

class DepthFirstTraverser<T> : BTVisitor<T>{
	public DepthFirstTraverser(BTNode<T> root, Action<BTNode<T>> action) : base(root, action){}
	
	public override void Visit(){
		var s = new Stack<BTNode<T>>();
		s.Push(_root);
		while(s.Any()){
			var current = s.Pop();
			if (current == null)
				continue;
			_action(current);
			s.Push(current.Right);
			s.Push(current.Left);
		}
	}
}

interface IVisitable<T>{
	void Accept(BTVisitor<T> visitor);
}

class BTNode<T> : IVisitable<T>
{
	public T Value { get; private set; }
	
	public BTNode<T> Left {get; set;}
	public BTNode<T> Right {get; set;}
	
	public BTNode(T value){
		Value = value;
	}
	
	public void Insert(BTNode<T> left, BTNode<T> right){
		Left = left;
		Right = right;
	}
	
	public void Accept(BTVisitor<T> visitor){
		visitor.Visit();
	}
}

/*
    Output:
    
    Breath-first traversal
    1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 

    Depth-first traversal
    1 2 4 8 9 5 10 11 3 6 12 13 7 14 15
*/