Leetcode discuss: 314. Binary Tree Vertical Order Traversal

 March 8, 2022

Here is the link. 

C# | Preorder traversal | Record total count, horizontal, level in the tree

Marhc 6, 2022
Introduction
It is easy for me to figure out how to traverse the tree, and also record horizontal position for each node, and preorder traversal should maintain the order of same row nodes in left to right order, but the code failed the test case 201/214. It cannot maintain the order of nodes in terms of level in the tree.

Test case 201/214 | First submission | Change design to add more tracking
201 / 214 test cases passed.
Input:
[3,9,8,4,0,1,7,null,null,null,2,5]
Output:
[[4],[9,5],[3,0,1],[2,8],[7]]
Expected:
[[4],[9,5],[3,0,1],[8,2],[7]]
I learned from the above failed test case. I need to maintain the order in the level of tree.
Tree node with value 2 and 8, node with value 8 is root node's right child, level is 1; whereas node with value 2 is the root's left.right.right, level is 3.

I decided to change the design, and record tree node's level in the tree, and also count of nodes in the tree. The comparison of tree node is up to 3 dimensions, Tuple<int, int, int>. Since second integer is the count of nodes which is unique, there will be no comparison in the third item - value of tree node.

The following C# code passes online judge.

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

namespace _314_Binary_tree_veritcal_order
{
    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 node3 = new TreeNode(3);
            node3.left = new TreeNode(9);
            node3.right = new TreeNode(20);
            node3.right.left = new TreeNode(15);
            node3.right.right = new TreeNode(7);

            var test = new Program();
            var result = test.VerticalOrder(node3);
            Debug.Assert(string.Join(",", result[0]).CompareTo("9") == 0);
            Debug.Assert(string.Join(",", result[1]).CompareTo("3,15") == 0);            
        }

        public IList<IList<int>> VerticalOrder(TreeNode root)
        {
            if (root == null)
                return new List<IList<int>>(); 

            var map = new Dictionary<int, List<Tuple<int, int, int>>>();

            var total = 0; 
            runPreOrderTraversal(root, map, ref total, 0, 0);

            var keys = map.Keys.ToList();
            var min = keys.Min();
            var max = keys.Max();

            var result = new List<IList<int>>(); 
            for (int i = min; i <= max; i++)
            {
                var items = map[i];
                items.Sort();

                var list = new List<int>();
                foreach (var item in items)
                {
                    list.Add(item.Item3);
                }

                result.Add(list);
            }

            return result; 
        }

        /// <summary>
        /// Argument:
        /// Just make sure that order is top to down, left to right; so preorder traversal should work. 
        /// Fail test case 201/214
        /// Need to sort nodes by level in the tree as well
        /// </summary>
        /// <param name="root"></param>
        /// <param name="map"></param>
        /// <param name="hIndex"></param>
        private void runPreOrderTraversal(TreeNode root, Dictionary<int, List<Tuple<int, int, int>>> map, ref int total, int hIndex, int level)
        {
            if (root == null)
                return;

            if (!map.ContainsKey(hIndex))
            {
                map.Add(hIndex, new List<Tuple<int, int, int>>());
            }

            map[hIndex].Add(new Tuple<int, int, int>(level, total, root.val));
            total++;

            runPreOrderTraversal(root.left, map,  ref total, hIndex - 1, level + 1);
            runPreOrderTraversal(root.right, map, ref total, hIndex + 1, level + 1); 
        }
    }
}