987. Vertical Order Traversal of a Binary Tree

Here is my discussion post.

C# Avoid using hashmap and sorting practice in 2020

It is challenge for me to understand how to master the algorithm and stay humble when I work on the algorithm I practice before. This week the mock interviewer on interviewing.io asked me to work on the algorithm, after he reviewed my solution using C# Dictionary and sorting based on hashMap's keys, he said that there is no need to use hashMap, no need to apply sorting.

The optimal time complexity can be achieved by using bucket sort.

Here are highlights of my practice.

1. Design a variable xValue, go to left child decrement one, go to right child increment one;
2. Traverse the tree to record maximum and minimum value of horizontal positions;
3. Declare an array of List, apply preorder traversal to visit every node in the tree, and save it into sorted variable based on horizontal value.
4. Stay humble, practice one using the optimal time complexity solution O(N).

/**
 * 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<IList<int>> VerticalTraversal(TreeNode root) 
    {
        if(root == null)
        {
            return new List<IList<int>>();           
        }
        
        var max = new int[2]{int.MaxValue, int.MinValue};
        
        traversalTree(root, max, 0);
        
        var size = max[1] - max[0] + 1; 
        
        var sorted = new List<int>[size];
        for(int i = 0; i < size; i++)
            sorted[i] = new List<int>(); 
        
        preorderTraveral(root, sorted, -max[0]);
         
        var sortedList = new List<IList<int>>();                        
        
        for(int i = 0; i < size; i++)
        {
            var list = new List<int>(); 
            foreach(var item in sorted[i])
            {
                list.Add(item); 
            }
            
            sortedList.Add(list); 
        }
        
        return sortedList; 
    }
    
    private void preorderTraveral(TreeNode root, List<int>[] sorted, int xValue)
    {
        if(root == null)
            return;
        sorted[xValue].Add(root.val);  
        
        preorderTraveral(root.left,  sorted, xValue - 1);
        preorderTraveral(root.right, sorted, xValue + 1);                             
    }
    
    private void traversalTree(TreeNode root, int[] max, int xValue)
    {
        if(root == null)
            return; 
        
        max[0] = max[0] > xValue? xValue : max[0];
        max[1] = max[1] < xValue? xValue : max[1]; 
        
        traversalTree(root.left,  max, xValue - 1);
        traversalTree(root.right, max, xValue + 1);                
    }
}