# Binary tree inorder traversal (iterative solution)

Problem statement

Given a binary tree, traversal the binary tree using inorder traversal, so the left child is visited first, and then node and then right child. Write an iterative solution as a practice of depth first search.

Algorithm

I like to practice the iterative solution of binary tree inorder traversal, since it is very easy to make a few mistakes in the first writing, I forgot to set the node is visited, and then I did not use Stack's Peek API and just use Pop. It is a good practice to write an iterative solution compared to recursive solution.

using System;
using System.Collections.Generic;
using System.Diagnostics;

namespace BinaryTree_InOrderTraversal
{
/// <summary>
/// binary tree iterative version of inorder traversal
/// </summary>
class Node
{
public  int  Value {  get; set; }
public  Node Left  {  get; set; }
public  Node Right {  get; set; }

public Node(int value)
{
Value = value;
}

static void Main(string[] args)
{
RunSampleTestcase();
}

/// <summary>
///       4
///   2       6
/// 1   3   5   7
/// | | | | | | |
/// 1 2 3 4 5 6 7
/// inorder traversal of binary tree is 1 2 3 4 5 6 7
/// the rehearsal of inorder traversal using the above binary tree.
///
/// Start from root node 4, push the node 4 into stack (stack is )
/// Get into while loop if stack is not empty
/// peek the stack, if the node's left child is not empty, and the left child is
/// unvisited status, then get into a loop push left child to the end.
/// For the above test case, two nodes are pushed into the stack consecutively.
///
/// push 2 to the stack ( stack [4, 2] )
/// push 1 to the stack ( stack [4, 2, 1] )
///
/// pop stack, visit node 1, mark node 1 is visited ( stack [4, 2] )
/// add node 1's right child if not null - node 1 does not have right child
/// continue the while loop
///
/// </summary>
public static void RunSampleTestcase()
{
var root = new Node(4);
root.Left = new Node(2);
root.Right = new Node(6);

root.Left.Left = new Node(1);
root.Left.Right = new Node(3);

root.Right.Left = new Node(5);
root.Right.Right = new Node(7);

var numbers = inorderTraversal(root);
Debug.Assert(string.Join(",", numbers).CompareTo("1,2,3,4,5,6,7") == 0);
}

/// <summary>
/// binary search tree inorder traversal using iterative solution
/// Easy to underestimate the complexity - better to use recursive function
///
/// Depth first search - great drill to practice
/// Write down the steps for the practice to deal with the stack:
/// If the stack is not empty, then
/// step 1: peek the stack for the top node
/// step 2: if the node peeked has left child and
/// the child node is not visited before, push the left child to the end.
///
/// Be careful that the backtracking process - second visit
///
/// step 3: pop the node from the stack
/// step 4: add visited node to the output
/// step 5: mark the visited node as visited.
/// step 6: deal with right child if there is one
///
/// Time complexity analysis:
/// Each node is visited twice. O(N), N is the total of nodes in the tree
///
/// </summary>
/// <param name="node"></param>
/// <returns></returns>
private static IList<int> inorderTraversal(Node node)
{
IList<int> nodes = new List<int>();
if (node == null)
{
return nodes;
}

var stack = new Stack<Node>();
stack.Push(node);

var visited = new HashSet<Node>();

while (stack.Count > 0)
{
// peek first, if need, continue to push left child to the stack
var current = (Node)stack.Peek();
var left = current.Left;

// push left to the end because it is downwarding process
while (left != null && !visited.Contains(left))
{
stack.Push(left);
left = left.Left;
}

var visit = stack.Pop();

if (visit.Right != null)
{
stack.Push(visit.Right);
}
}

return nodes;
}
}
}


• Based on the .NET Naming Guidelines methods should be named using PascalCase casing, hence inorderTraversal should be named InorderTraversal.
• var current = (Node)stack.Peek(); there is no need to cast here because a Stack<Node> will return a Node if there is one.