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.
Here is the C# practice. Please help me review the code.
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 [4])
/// 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
/// - add HashSet to mark the visit to avoid deadloop
///
/// 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();
nodes.Add(visit.Value);
visited.Add(visit);
if (visit.Right != null)
{
stack.Push(visit.Right);
}
}
return nodes;
}
}
}
