Archive for the ‘ Tree ’ Category

Iterative Method for Finding Height Of Tree

For finding the height of the tree we can use level order traversal of three. We  need to traverse the tree level by level and increment the height count.

        public int IterativeHeightOfTree(TreeNode root)
        {
            int height = 0;
            if (root == null)
            {
                return height;
            }
            int nodes = 0;
            Queue<TreeNode> queue = new Queue<TreeNode>();
            queue.Enqueue(root);
 
            while (true)
            {
                nodes = queue.Count();
                if (nodes == 0)
                {
                    return height;
                }
                height = height + 1;
                while (nodes > 0)
                {
                    var temp = queue.Dequeue();
                    if (temp.Left != null)
                    {
                        queue.Enqueue(temp.Left);
                    }
                    if (temp.Right != null)
                    {
                        queue.Enqueue(temp.Right);
                    }
                    nodes = nodes - 1;
                }
 
            }
 
            //return height;
        }

Test Case

Tree Node count is :  20
5,3,9,15,13,9,7,18,2,13,1,5,7,19,13,13,6,12,14,14,
Height of Tree is 5

Tree Node count is :  1
1,
Height of Tree is 1

Tree Node count is :  0
Height of Tree is 0

Tree Traversal Pre-Order Iterative

We have already have post on various tree traversal in recursive way. Today we will cover how we can traverse a tree in iterative way.

Iterative Pre order tree traversal : For this we will be using stack to keep track of the traversed nodes

        public void iterativePreorder(TreeNode node)
        {

            bool done = false;
            Stack<TreeNode> parentStack = new Stack<TreeNode>();
            while (!done)
            {
                if (node == null && parentStack.Count() == 0)
                {
                    done = true;
                    return;
                }
                if (node != null)
                {
                    Console.Write(node.Data + " >");
                    parentStack.Push(node.Right);
                    node = node.Left;
                }
                else
                {
                    node = parentStack.Pop();
                }

            }
        }

Tree Traversal In-Order Iterative

We have already have post on various tree traversal in recursive way. Today we will cover how we can traverse a tree in iterative way.

Iterative in order tree traversal : For this we will be using stack to keep track of the traversed nodes.

        public void IterativeInorder(TreeNode node)
        {
            Stack<TreeNode> parentStack = new Stack<TreeNode>();

            bool done = false;
            while (!done)
            {
                if (node == null && parentStack.Count() == 0)
                {
                    done = true;
                    return;
                }
                if (node != null)
                {
                    parentStack.Push(node);
                    node = node.Left;
                }
                else
                {
                    var temp = parentStack.Pop();
                    Console.Write(temp.Data + " >");
                    node = temp.Right;
                }
            }
            Console.WriteLine();
        }

Tree Traversal In-order, Pre-order and Post-order:Recursive

public class TreeNode
    {
        public int Data { get; set; }
        public TreeNode Left { get; set; }
        public TreeNode Right { get; set; }
    }

In-Order

public void Inorder(TreeNode node)
        {
            if (node == null)
            {
                return;
            }
            Inorder(node.Left);
            Console.Write(node.Data + " >");
            Inorder(node.Right);
        }

Pre-Order

public void Preorder(TreeNode node)
        {
            if (node == null)
            {
                return;
            }
            Console.Write(node.Data + " >");
            Preorder(node.Left);
            Preorder(node.Right);
        }

Post-Order

public void Postorder(TreeNode node)
   {
       if (node == null)
       {
           return;
       }

       Postorder(node.Left);
       Postorder(node.Right);
       Console.Write(node.Data + " >");
   }