Program to Implement recursive and Iterative Binary Tree Traversal – Preorder, InOrder and Postorder

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;

        }

    }