## Archive for the ‘ Tree ’ Category

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```

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();
}

}
}```

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();
}```

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 + " >");
}