Skip to main content

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;

        }

    }

Comments

Popular posts from this blog

Git fundamental and useful command to use - version-2

      Install Git your local machine Link: Git - Downloads (git-scm.com) Version : git version 2.31.1.windows.1   Know the version $ git --version   Git help for command $ git help config $ git config --help Prompt the git config help file in browser Make a directory $ mkdir shubhapp$ mkdir shubhapp $ cd shubhapp/ - go to directory   initialize the git $ git init Initialized empty Git repository in C:/Users/shubh/shubhapp/.git/   Create a file Hello.txt   Add this file to git $ git Add hello.txt   Commit the changes $ git commit -a -m "commit comment"   Connect to remote github $ git config --global user.username shubh-techie  

Min Cost to Connect Ropes problem solution using PriorityQueue using C#

Given n ropes of different lengths, we need to connect these ropes into one rope. We can connect only 2 ropes at a time. The cost required to connect 2 ropes is equal to sum of their lengths. The length of this connected rope is also equal to the sum of their lengths. This process is repeated until n ropes are connected into a single rope. Find the min possible cost required to connect all ropes. Input: ropes = [ 8 , 4 , 6 , 12 ] Output: 58 Explanation: The optimal way to connect ropes is as follows 1. Connect the ropes of length 4 and 6 (cost is 10 ). Ropes after connecting: [ 8 , 10 , 12 ] 2. Connect the ropes of length 8 and 10 (cost is 18 ). Ropes after connecting: [ 18 , 12 ] 3. Connect the ropes of length 18 and 12 (cost is 30 ). Total cost to connect the ropes is 10 + 18 + 30 = 58 public static void Demo() { //int[] Ropes = { 4, 3, 2, 6 }; //int[] Ropes = { 8, 4, 6, 12 }; int[] Ropes = { 1, 2, 5, 10, 35, 89

Given an array of integers, and a target value determine if there are two integers that add to the sum using C#

Given an array of integers, and a target value determine if there are two integers that add to the sum.