Vertical Order Traversal in using Level Order Concept of Binary Tree

Question

I want to traverse a Binary Tree vertically. And I found a working code in Geeks for Geeks in C++. I want to convert it into C# but I am unable to do so. Please guide me.

Below is my attempt:

// we always need the address of the Root Node come what may!
public class BstNode
{
    public int data      { get; set; }
    public BstNode left  { get; set; }
    public BstNode right { get; set; }

    public BstNode(int value) => data = value;
}

public class BstTree
{
    // For BST
    public BstNode Insert(BstNode root, int data)
    {
        if (root == null)
        {
            root       = new BstNode(data);
            root.left  = null;
            root.right = null;
        }
        else if (data > root.data)
             root.right = Insert(root.right, data);
        else root.left = Insert(root.left, data);

        return root;
    }
    // PROBLEM IN BELOW CODE
    public void VerticalOrderTraverse(BstNode root)
    {
        // Base case
        if (root == null)
            return;

        // Create a map and store vertical oder in
        Dictionary<int, List<int>> dict = new Dictionary<int, List<int>>();
        int hd = 0;

        // Create queue to do level order traversal.
        // Every item of queue contains node and
        // horizontal distance.
        Queue<Tuple<BstNode, int>> que = new Queue<Tuple<BstNode, int>>();
        que.Enqueue(new Tuple<BstNode, int>(root, hd));
        while (que.Count != 0)
        {
            // pop from queue front
            Tuple<BstNode, int> temp = que.Peek();
            que.Dequeue();
            hd = temp.Item2;
            BstNode node = temp.Item1;

            // insert this node's data in vector of hash
            dict.Add(hd, new List<int>(node.data)); // CONFUSED HERE

            if (node.left != null)
                que.Enqueue(new Tuple<BstNode, int>(node.left, hd - 1));
            if (node.right != null)
                que.Enqueue(new Tuple<BstNode, int>(node.right, hd + 1));
        }
        foreach (var item in dict)
            foreach (var ite in item.Value)
                Console.WriteLine(ite);
    }
}

class Program
{
    public static void Main()
    {
        BstNode root = null;
        BstTree bstTree = new BstTree();
        root = bstTree.Insert(root, 10);
        root = bstTree.Insert(root, 12);
        root = bstTree.Insert(root, 7);
        root = bstTree.Insert(root, 8);
        root = bstTree.Insert(root, 15);
        root = bstTree.Insert(root, 11);
        root = bstTree.Insert(root, 6);
        bstTree.VerticalOrderTraverse(root);
    }
}

Kindly note that I am getting exception in "VerticalOrderTraversal" Method. This VerticalOrderTraversal is exact replica of Vertical Order Traversal in C++

Exception: Key already exists in dictionary

EDIT:

After adding this check still the Logic does not give correct output

if (dict.ContainsKey(hd))
     dict[hd].Add(node.data);
else dict.Add(hd, new List<int>(node.data));

And what do you understand by that error message? Don't blindly copy-paste code you don't understand — Camilo Terevinto, Jun 03 '18 at 22:13
What!!! I did not blindly copy paste the code. Cummon. I read it in geeks and converted in in c# and trying to understand it now. — Unbreakable, Jun 03 '18 at 22:14
I am getting error of keys already present. I can always put a check for key but that will break the logic for the traversal — Unbreakable, Jun 03 '18 at 22:14
You need to take the time to debug your code line by line if you want to understand it. We cannot help you with this. — Camilo Terevinto, Jun 03 '18 at 22:15
If you dont consider this question, has been put in effort then I am not sure how you want the question to be put. I have added the links I have added the exception what else you want from me — Unbreakable, Jun 03 '18 at 22:15
@CamiloTerevinto: I had added this check `if(!dict.ContainsKey(hd))` but that breaks the logic — Unbreakable, Jun 03 '18 at 22:18
@CamiloTerevinto: A dictionary in C# cannot contains duplicate keys. Thats what I understood from error. :-| — Unbreakable, Jun 03 '18 at 22:21
a C# Dictionary is not necessarily the same as a map in the C++ version. which datastructure is used in the original, and what are its properties? You need to use a data structure that has the same way of dealing with duplicate keys, or find the error that it causing it to encounter duplicates, in case the original code does not. — Cee McSharpface, Jun 03 '18 at 22:22
https://stackoverflow.com/questions/21183414/what-is-c-sharp-equivalent-of-map-in-c this link suggested that I can use Dictionary. :-| — Unbreakable, Jun 03 '18 at 22:23
concerning your edit, @Unbreakable: you seem to have achieved a pretty good port of the C++ code so far. Are you aware that your test data is different from the original? The only significant difference I can see is that a `map` is [ordered by its keys](https://stackoverflow.com/q/2196995/1132334), while a `Dictionary` is not. Replace `Dictionary` by `SortedDictionary` and let us know if that helps. otherwise, explain "not ... correct output". — Cee McSharpface, Jun 04 '18 at 01:59

score 0 · Answer 1 · edited Jun 04 '18 at 01:35

Where you have this:

dict.Add(hd, new List<int>(node.data));

The original has this:

m[hd].push_back(node->key);

Now when we look up in documentation what the operator std::map::operator[] does, we find that

If k matches the key of an element in the container, the function returns a reference to its mapped value.

and importantly,

If k does not match the key of any element in the container, the function inserts a new element with that key

The indexer of Dictionary<TKey, TValue>.Item has the same capability ("a set operation creates a new element with the specified key"), but whereas in C++, this implies construction of a new vector as the value of the new element, C# does not create an instance of List<int> for us, so a simple solution could be:

if (dict.ContainsKey(hd))
     dict[hd].Add(node.data);
else dict.Add(hd, new List<int>(node.data));

@Austin, I will not start an edit war over bracing preferences, just my personal opinion is that if we must omit braces for single-liners, we should at least break-and-indent the statement in the else clause too. — Cee McSharpface, Jun 04 '18 at 01:44
You mean the `else` statement body on it's own line? Sure, we can meet halfway. I just try to keep things condensed so we're not scrolling so much — AustinWBryan, Jun 04 '18 at 02:18

score 0 · Answer 2 · answered Sep 20 '18 at 03:45

 /// <summary>
    /// We must calculate horizontal distance.
    /// Each node along with its hd shall be queued.
    /// Add hd and values in one hashset.
    /// </summary>
    /// <param name="root"></param>
    public void VerticalOrderTraversal(Node<T> root)
    {
        if (root == null)
            return;

        int hd = 0;
        Queue<Tuple<Node<T>,int>> q = new Queue<Tuple<Node<T>,int>>();
        Dictionary<int, HashSet<T>> ht = new Dictionary<int, HashSet<T>>();
        q.Enqueue(new Tuple<Node<T>, int>(root,hd));
        ht[hd] = new HashSet<T>();
        ht[hd].Add(root.Data);
        while (q.Count > 0)
        {
            Tuple<Node<T>, int> current = q.Peek();
            q.Dequeue();

            if (current.Item1.leftNode != null)
            {
                if (!ht.ContainsKey(current.Item2 -1))
                {
                    ht[current.Item2 - 1] = new HashSet<T>();
                    ht[current.Item2 - 1].Add(current.Item1.leftNode.Data);
                }
                else
                {
                    ht[current.Item2 - 1].Add(current.Item1.leftNode.Data);
                }
                q.Enqueue(new Tuple<Node<T>, int>(current.Item1.leftNode, current.Item2 - 1));


            }
            if (current.Item1.rightNode != null)
            {
                if (!ht.ContainsKey(current.Item2 + 1))
                {
                    ht[current.Item2 + 1] = new HashSet<T>();
                    ht[current.Item2 + 1].Add(current.Item1.rightNode.Data);
                }
                else
                {
                    ht[current.Item2 + 1].Add(current.Item1.rightNode.Data);
                }
                q.Enqueue(new Tuple<Node<T>, int>(current.Item1.rightNode, current.Item2 + 1));

            }
        }

        foreach (int key in ht.Keys)
        {
            foreach (T data in ht[key])
            {
                Console.WriteLine("Vertical Level " + key + " value " + data);
            }
        }
    }

Please try this. It may help – Gaurav Bhushan Sep 20 '18 at 03:47 — Gaurav Bhushan, Sep 20 '18 at 03:47

score 0 · Answer 3 · edited Aug 04 '20 at 09:21

there are few changes I made to the original code:

If the level (hd) already exists in the Dict, we need to add the node to the end of the list not to insert a new tuple of level and list. so I added the if statement [if (dict.ContainsKey(hd))]
better use a sorted dictionary so that print will be from the least level not from the first level that was inserted.

In the original code, the list was created while inserting into the Dict, that was an issue because the node.data would be taken as the capacity of the list not as a data in the list.

 public void VerticalOrderTraverse(BstNode root)
         {
             // Base case
             if (root == null)
                 return;

             // Create a map and store vertical oder in
             SortedDictionary<int, List<int>> dict = new SortedDictionary<int, List<int>>();     //used Sorted Dictionary
             int hd = 0;

             Queue<Tuple<BstNode, int>> que = new Queue<Tuple<BstNode, int>>();
             que.Enqueue(new Tuple<BstNode, int>(root, hd));
             while (que.Count != 0)
             {
                 Tuple<BstNode, int> temp = que.Peek();
                 que.Dequeue();
                 hd = temp.Item2;
                 BstNode node = temp.Item1;

                 if (dict.ContainsKey(hd))  //No need to try creating a new list, add it to the existing 
                     dict[hd].Add(node.data);
                 else
                 {
                     dict.Add(hd, new List<int>()); 
                     dict[hd].Add(node.data);
                 }
                 if (node.left != null)
                     que.Enqueue(new Tuple<BstNode, int>(node.left, hd - 1));
                 if (node.right != null)
                     que.Enqueue(new Tuple<BstNode, int>(node.right, hd + 1));
             }

             foreach (var item in dict)
                 foreach (var ite in item.Value)
                     Console.WriteLine(ite);
         }
     }
 }
}

1. If the level (hd) already exists in the Dict, we need to add the node to the end of the list not to insert a new tuple of level and list. so I added the if statement 2. better use a sorted dictionary so that print will be from the least level not from the first level that was inserted. 3. In the original code, the list was created while inserting into the Dict, that was an issue because the node.data would be taken as the capacity of the list not as a data in the list. — Yasaman shm, Jul 05 '19 at 03:08

score 0 · Answer 4 · answered Aug 08 '21 at 19:35

public class Solution {
    
    public IList<IList<int>> result = new List<IList<int>>();
    public SortedDictionary<int, List<int>> IndexingItems = new SortedDictionary<int, List<int>>();
        
    public IList<IList<int>> VerticalTraversal(TreeNode root)
    {
        if(root == null) return result;
        Queue<(int, TreeNode)> queue = new Queue<(int, TreeNode)>();
        int hDis = 0;
        queue.Enqueue((hDis, root));
        
        while(queue.Count != 0)
        {
            (int, TreeNode) qTop = queue.Peek();
            queue.Dequeue();
            hDis = qTop.Item1;
            TreeNode current = qTop.Item2;
            AddItemToDictionary(hDis, current);
            
            if(current.left != null)
            {
                queue.Enqueue((hDis - 1, current.left));
            }
            
            if(current.right != null)
            {
                queue.Enqueue((hDis + 1, current.right));
            }
        }
        
        foreach(var item in IndexingItems)
        {
            var value = item.Value as List<int>;            
            result.Add(value);
        }
        return result;
    }
    
    public void AddItemToDictionary(int hDis, TreeNode node)
    {
        if(IndexingItems.ContainsKey(hDis))
        {
            IndexingItems[hDis].Add(node.val);
            // Console.WriteLine($"Updating {hDis} value");
        }
        else
        {
            // Console.WriteLine($"Adding new item {hDis} to Dictionary with {node.val} value");
            IndexingItems.Add(hDis, new List<int>(){ node.val });
        }
    }
}

I tried with this approach. But I am not sure, why there is a few mismatch in the order of the data for same nodes.

Vertical Order Traversal in using Level Order Concept of Binary Tree

4 Answers4