The example Draw a breadth-first colored binary tree in C# shows how to use a `Stack` to draw a binary tree in depth-first order. The program builds a `Stack` representing the bottom (trunk) level of the tree. For each level, it processes the `Stack`, adding child branches for the next level to a new `Stack`.

This example shows how you can use a `Queue` to implement a slightly simpler approach. The following code shows the `BranchInfo` class that the program uses to hold information about a branch that it will later draw.

// Hold branch information. private class BranchInfo { public float X, Y, Theta, Length; public int Depth; public BranchInfo(float x, float y, float theta, float length, int depth) { X = x; Y = y; Theta = theta; Length = length; Depth = depth; } }

This object holds a branch’s starting position, direction, length, and depth in the tree.

The following code shows how the program draws its tree.

// Draw a binary tree. private void DrawTree(Graphics gr, Pen pen, int max_depth, float x, float y, float max_length, float initial_theta, float length_scale, float dtheta) { // Add the trunk to a queue. Queue<BranchInfo> branches = new Queue<BranchInfo>(); branches.Enqueue(new BranchInfo(x, y, initial_theta, max_length, max_depth)); // Process branches until the queue is empty. while (branches.Count > 0) { // Draw the next branch. BranchInfo branch = branches.Dequeue(); // Set the pen's color depending on the depth. if (branch.Depth == 1) pen.Color = Color.Red; else { int g = 255 * (max_depth - branch.Depth) / max_depth; int r = 139 * (branch.Depth - 3) / max_depth; if (r < 0) r = 0; int b = 0; pen.Color = Color.FromArgb(r, g, b); } // Set the pen's thickness depending on the depth. int thickness = 10 * branch.Depth / max_depth; if (thickness < 0) thickness = 0; pen.Width = thickness; // See where this branch should end. float x1 = (float)(branch.X + branch.Length * Math.Cos(branch.Theta)); float y1 = (float)(branch.Y + branch.Length * Math.Sin(branch.Theta)); // Draw the branch. gr.DrawLine(pen, branch.X, branch.Y, x1, y1); // If branch.depth > 1, add child branches to the queue. if (branch.Depth > 1) { branches.Enqueue(new BranchInfo(x1, y1, branch.Theta + dtheta, branch.Length * length_scale, branch.Depth - 1)); branches.Enqueue(new BranchInfo(x1, y1, branch.Theta - dtheta, branch.Length * length_scale, branch.Depth - 1)); } } }

The method starts by creating a `Queue` and adding a new `BranchInfo` object to it to represent the tree’s trunk. It then enters a `while` loop that executes as long as the `Queue` isn’t empty.

Inside the loop, the code calls the `Queue`‘s `Dequeue` method to get the next item from the queue. In a `Queue`, items are added and removed in first-in-first-out or FIFO order. That means the `Dequeue` method returns the item that has been in the queue the longest. (This is the way a line (or queue if you’re British) works when you’re waiting for the bus.)

The program draws the branch that was just removed from the `Queue`. Then if the branch’s depth is greater than 1, the code adds the branch’s children to the `Queue`.

The program repeats the `while` loop until the `Queue` is empty.

Inside the `Queue`, all of the branches of a given depth are grouped together. To see why, consider that initially the trunk is the only branch and suppose it has depth 10.

When the program processes the trunk, it adds two branches of depth 9. They are the only branches in the `Queue`, so they are grouped together.

Next the program processes the two depth 9 branches and adds their children to the end of the `Queue`. Because they go at the end and the existing branches are at the front of the `Queue`, the depth 8 children are grouped together at the end.

More generally, suppose the program has removed all of the branches of depth D and the `Queue` contains only branches of depth D – 1. They are all at the front of the `Queue`. As it processes those branches, the code adds branches at depth D – 2 to the end of the `Queue`. They all come after the depth D – 1 branches, so they are grouped, too.

Eventually the `Queue` contains branches of depth 1. When the program processes them, it doesn’t add child branches to the `Queue` so the `Queue` empties out and the loop ends.