94. Binary Tree Inorder Traversal

August 23, 2022

Here is the link. 

C# | Quick learner | using recursive function or stack

August 23, 2022

I like to write a working solution using recursive function, and review my last practice back in 2018.

Solution 1:
I choose to use C# List and also write a function to pass List as a function argument, so all nodes in the tree will be visited once and be added to List in inorder traversal order.

Space complexity: Using O(N) space, List
Time complexity: O(N), N is the total number of nodes in the tree

using System;
using System.Collections.Generic;
using System.Diagnostics;
using System.Linq;
using System.Text;
using System.Threading.Tasks;

namespace _94_inorder_traversal
{
    class Program
    {
        public class TreeNode {
            public int val;
            public TreeNode left;
            public TreeNode right;
            public TreeNode(int val=0, TreeNode left=null, TreeNode right=null) {
                this.val = val;
                this.left = left;
                this.right = right;
            }
        }

        static void Main(string[] args)
        {
            var root = new TreeNode(1);
            root.right = new TreeNode(2);
            root.right.left = new TreeNode(3);
            var list = InorderTraversal(root);
            Debug.Assert(string.Join(",", list).CompareTo("1,3,2") == 0); 
        }

        /// <summary>
        /// emtpy tree, with one root node, with more nodes
        /// </summary>
        /// <param name="root"></param>
        /// <returns></returns>
        public static IList<int> InorderTraversal(TreeNode root) 
        {
            var list = new List<int>();
            runInorderTraversal(root, list);

            return list;             
        }

        private static void runInorderTraversal(TreeNode root, IList<int> list)
        {
            if (root == null)
            {
                return;
            }

            runInorderTraversal(root.left, list);
            list.Add(root.val);
            runInorderTraversal(root.right, list);
        }
    }
}

Solution 2 | Using stack | iterative solution
I think that the design should be simple. Go over a few test cases, and then complete the design.

using System;
using System.Collections.Generic;
using System.Diagnostics;
using System.Linq;
using System.Text;
using System.Threading.Tasks;

namespace _94_inorder_traversal_iterative
{
    class Program
    {
        public class TreeNode
        {
            public int val;
            public TreeNode left;
            public TreeNode right;
            public TreeNode(int val = 0, TreeNode left = null, TreeNode right = null)
            {
                this.val = val;
                this.left = left;
                this.right = right;
            }
        }

        static void Main(string[] args)
        {
            var root = new TreeNode(1);
            root.right = new TreeNode(2);
            root.right.left = new TreeNode(3);
            var list = InorderTraversal(root);
            Debug.Assert(string.Join(",", list).CompareTo("1,3,2") == 0);
        }
       
        /// <summary>
        /// study code
        /// 
        /// </summary>
        /// <param name="root"></param>
        /// <returns></returns>
        public static IList<int> InorderTraversal(TreeNode root)
        {
            var list = new List<int>();

            if (root == null)
            {
                return list;
            }

            // stack - inorder - left, root, right
            var stack = new Stack<TreeNode>();
            var current = root;

            // stack 
            // design - visit left child and right child at least once
            // put left child first, before root node itself. 
            // stack.Push - only once - in coding writing
            // stack.Pop - only once - in coding writing
            // 
            while (stack.Count > 0 || current != null)
            {
                // Go over an example
                // Binary tree - Test case 1: 
                // root = new TreeNode(1);
                // root.left = new TreeNode(2);
                // root.left.left = new TreeNode(3);
                // nodes should be pushed into stack: push 1, push 2, push 3
                // Work on test case 1, and then add a right node into tree, work on test case 2 to cover all test cases. 
                while (current != null)
                {
                    stack.Push(current);
                    current = current.left;
                }

                // Pop()
                current = stack.Pop();
                list.Add(current.val);

                // Go to right
                current = current.right;
            }

            return list;
        }
    }
}

Solution 3:

Oct. 4, 2018
It is a medium level tree algorithm. I submitted the solution more than four months ago. I like to review the code before I start to work on other 20 medium level tree algorithms. It is also a good idea to share here.

/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     public int val;
 *     public TreeNode left;
 *     public TreeNode right;
 *     public TreeNode(int x) { val = x; }
 * }
 */
public class Solution {
    public IList<int> InorderTraversal(TreeNode root) // emtpy tree, with one root node, with more nodes
        {
            if (root == null)
            {
                return new List<int>(); 
            }

            var left = InorderTraversal(root.left);
            left.Add(root.val);
            var right = InorderTraversal(root.right);

            // add right to left list <- code review on August 23, 2022, it is not a good practice. 
            if (right.Count > 0)
            {
                foreach (var item in right)
                {
                    left.Add(item);
                }
            }

            return left; 
    }
}

I think that it is better to avoid copying the list from right variable to left. It takes extra time and no need to do that.