Breadth-First and Depth-First Traversal of a C# Binary Search Tree

In several recent posts I’ve presented C# code for a binary search tree where each data value is a (long) integer. Here is some additional code that shows how to traverse a tree in breadth-first and depth-first traversals.

public void DisplayBF()
{
// breadth-first using a queue
Queue<TreeNode> q = new Queue<TreeNode>();
q.Enqueue(this.root);
while (q.Count > 0)
{
TreeNode n = q.Dequeue();
Console.WriteLine(n.data);
if (n.left != null)
q.Enqueue(n.left);
if (n.right != null)
q.Enqueue(n.right);
}
}

public void DisplayDF()
{
// depth-first using a stack
Stack<TreeNode> s = new Stack<TreeNode>();
s.Push(this.root);
while (s.Count > 0)
{
TreeNode n = s.Pop();
Console.WriteLine(n.data);
if (n.left != null)
s.Push(n.left);
if (n.right != null)
s.Push(n.right);
}
}

The code for the two methods is identical except that breath-first traversal uses a queue and depth-first traversal uses a stack. Calling the methods could look like:

BinarySearchTree bst = new BinarySearchTree();
bst.Insert(50); // level 0

bst.Insert(30); // level 1
bst.Insert(10); // level 2
bst.Insert(20); // level 3

bst.Insert(80); // level 1
bst.Insert(60); // level 2
bst.Insert(70); // level 3

bst.DisplayBF();
bst.DisplayDF();