Wednesday, May 25, 2016

Binary Tree Inorder traversal - Iterative solution - warm up practice

May 25, 2016

Review binary tree inorder iterative solution, add some test cases.


Questions and Answers:

1. How is the practice of inorder traversal iterative solution?

Julia compared to the other solution, line 354 - line 372, inOrderIterative_B

and chose this one to practice:


She wrote some comment to argue that the solution is very efficient and no redundant code. She likes to use reasoning and analysis to help her structure the function.

Here are her analysis: 
        
1. First, argue that line 88, why to check "if stack is empty, break the while loop" before outputting any node in the stack. Otherwise, if the stack is empty, then, line 91: execution run time error.

2. Second, argue that output of inorder traversal nodes is not in inner loop. If there are more than 1 in a row to output, then the outer while loop (line 79) will take care of it.
     
3. Third, argue that line 94: runner = runner.right;
It does not matter that right child exists or not, line 81 will take care of null. 

Complete one iteration -

Push nodes into stack, then first node in inorder is on the top of stack, If stack is empty, break; otherwise, ready to pop top one from the stack, and then, move runner to its right child.

Follow up after 12 months


March 27, 2017

Read the blog and think about the better presentation, more readable. 

Write another C# practice, and post a question about binary tree inorder traversal (iterative solution) for code review. 


   
      

No comments:

Post a Comment