Given a Binary tree, Traverse it using DFS using recursion. Therefore, the Depth First Traversals of this Tree will be:
(a) Inorder (Left, Root, Right)
(b) Preorder (Root, Left, Right)
(c) Postorder (Left, Right, Root)
public class DFSTraversalUtility
{
public static void PreOrder(TreeNode root)
{
if (root != null)
{
Console.Write(root.Data + " ");
PreOrder(root.Left);
PreOrder(root.Right);
}
}
public static void InOrder(TreeNode root)
{
if (root != null)
{
InOrder(root.Left);
Console.Write(root.Data + " ");
InOrder(root.Right);
}
}
public static void PostOrder(TreeNode root)
{
if (root != null)
{
PostOrder(root.Left);
PostOrder(root.Right);
Console.Write(root.Data + " ");
}
}
public static void PostOrderIterative(TreeNode root)
{
if (root != null)
{
Stack<TreeNode> track = new Stack<TreeNode>();
List<int> output = new List<int>();
TreeNode currNode = root;
while (currNode != null || track.Count > 0)
{
if (currNode != null)
{
output.Add(currNode.Data);
track.Push(currNode);
currNode =
currNode.Right;
}
else
{
currNode =
track.Pop().Left;
}
}
output.Reverse();
Console.WriteLine(string.Join(",
", output));
}
}
public static void PreOrderIterative(TreeNode root)
{
if (root != null)
{
Stack<TreeNode> track = new Stack<TreeNode>();
TreeNode currNode = root;
while (currNode != null || track.Count > 0)
{
if (currNode != null)
{
Console.Write(currNode.Data + " ");
track.Push(currNode);
currNode =
currNode.Left;
}
else
{
currNode =
track.Pop().Right;
}
}
}
}
public static void InOrderIterative(TreeNode root)
{
if (root != null)
{
Stack<TreeNode> track = new Stack<TreeNode>();
TreeNode currNode = root;
while (currNode != null || track.Count > 0)
{
if (currNode != null)
{
track.Push(currNode);
currNode =
currNode.Left;
}
else if (track.Count > 0)
{
currNode = track.Pop();
Console.Write(currNode.Data + " ");
currNode =
currNode.Right;
}
}
}
}
}
class Program
{
static void Main(string[] args)
{
TreeNode root = GetTreeRoot();
ShowAllTraversal(root);
Console.WriteLine("Please press <enter> to exit.");
Console.ReadLine();
}
private static void ShowAllTraversal(TreeNode root)
{
Console.WriteLine("===============================================");
Console.WriteLine("preorder traversal...");
DFSTraversalUtility.PreOrder(root);
Console.WriteLine("PreOrderIterative(root) traversal...");
DFSTraversalUtility.PreOrderIterative(root);
Console.WriteLine("===============================================");
Console.WriteLine("InOrder traversal...");
DFSTraversalUtility.InOrder(root);
Console.WriteLine("InOrderIterative (root) traversal...");
DFSTraversalUtility.InOrderIterative(root);
Console.WriteLine("===============================================");
Console.WriteLine("preorder traversal...");
DFSTraversalUtility.PostOrder(root);
Console.WriteLine("PostOrderIterative(root) traversal...");
DFSTraversalUtility.PostOrderIterative(root);
Console.WriteLine();
}
private static TreeNode
GetTreeRoot()
{
TreeNode root = new TreeNode(10)
{
Left = new TreeNode(20),
Right = new TreeNode(30)
};
root.Left.Left = new TreeNode(40);
root.Left.Right = new TreeNode(50);
root.Right.Left = new TreeNode(60);
root.Right.Right = new TreeNode(70);
return root;
}
}
public class TreeNode
{
public int Data;
public TreeNode Left;
public TreeNode Right;
public TreeNode(int data)
{
this.Data = data;
}
}