Given a binary tree we want to traverse the tree in different ways.
- Breadth First Search
- Depth First Search
Breadth First Search
This is also called level by level traversal of a binary tree starting from the root.
Given the node class as shown below
public class Node {
public int element;
public Node left;
public Node right;
public Node(int element, Node left, Node right) {
this.element = element;
this.left = left;
this.right = right;
}
}
We can use a queue to do the Breadth Frist traversal. Basically we start from the root node and add that to the queue.
We then iterates as long as the queue is not empty and we print the node and remove it from the queue.
public void BFS(Node root) {
Queue<Node> queue = new Queue<Node>();
queue.Enqueue(root);
while (!(queue.Count == 0)) {
Node node = queue.Peek();
if (node != null) {
Console.WriteLine(node.element + " ");
queue.Dequeue();
if (node.left != null)
queue.Enqueue(node.left);
if (node.right != null)
queue.Enqueue(node.right);
}
}
}
Depth First Search
We have three types of DFS.
- In order traversal
- Post order traversal
- pre order traversal
In order traversal
Print left child first, then the parent and then the right child
private void printTreeIn(Node t) {
if (t != null) {
printTreeIn(t.left);
Console.WriteLine(t.element);
printTreeIn(t.right);
}
}
Post order traversal
print left, right and lastly parent in that order
private void printTreePost(Node t) {
if (t != null) {
printTreePost(t.left);
printTreePost(t.right);
Console.WriteLine(t.element);
}
}
Pre order traversal
print parent, left and lastly right in that order
private void printTreePre(Node t) {
if (t != null) {
Console.WriteLine(t.element);
printTreePre(t.left);
printTreePre(t.right);
}
}