2
\$\begingroup\$

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;
        }
    }
}
\$\endgroup\$
1
\$\begingroup\$

In general I don't see anything plainly wrong with your code, but I have some small nit-picks:

  • 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.

\$\endgroup\$
  • \$\begingroup\$ Very good review. I did spend over one hour to review my first writing, with deadloop bug because of lacking visited checking in design, multiple calls of stack's Pop API inside while loop, extra checking using if statement before stack Pop API call. I will wait another 48 hours before I mark your review as an answer. \$\endgroup\$ – Jianmin Chen Mar 28 '17 at 6:08

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.