Find all duplicate levels of given Binary Tree

 

using System;

using System.Collections.Generic;

using System.Linq;

 

public class Node {

    public int data;

    public Node left, right;

    public Node(int item)

    {

        data = item;

        left = right = null;

    }

}

 

public class LevelInfo {

    public int level;

    public int length;

}

 

public class GFG {

 

    

    public Node root;

    Dictionary<int, List<LevelInfo> > duplicateMap

        = new Dictionary<int, List<LevelInfo> >();

 

    public virtual List<List<int> >

    printDuplicateLevels(Node root)

    {

        int h = height(root);

        int i;

 

        List<List<int> > dup_levels

            = new List<List<int> >();

 

        

        var zerolevelInfo

            = new LevelInfo() { level = 0,

                                length = 0 };

 

        duplicateMap[root.data]

            = new List<LevelInfo>() { zerolevelInfo };

 

        for (i = 1; i <= h; i++) {

            List<int> currentLevel

                = new List<int>();

            var currentLevelOrder

                = getCurrentLevel(root, i,

                                  currentLevel)

                      .ToList();

 

            int decimalValue = Convert.ToInt32(

                string.Join("", currentLevelOrder), 2);

 

            var currentlevelInfo = new LevelInfo() {

                level = i - 1, length

                               = currentLevelOrder.Count()

            };

 

            if (duplicateMap.ContainsKey(decimalValue)) {

                var dictData

                    = duplicateMap[decimalValue].Where(

                        l => l.length

                            == currentLevelOrder.Count());

                if (dictData.Any()) {

                    List<int> dup_level_curr

                        = new List<int>();

                    dup_level_curr.Add(i - 1);

                    dup_level_curr.Add(

                        dictData.Select(l => l.level)

                            .First());

                    dup_levels.Add(dup_level_curr);

                }

                else {

                    duplicateMap[decimalValue].Add(

                        currentlevelInfo);

                }

            }

            else

                duplicateMap[decimalValue]

                    = new List<LevelInfo>() {

                          currentlevelInfo

                      };

        }

 

        return dup_levels;

    }

 

    

    public virtual int height(Node root)

    {

        if (root == null) {

            return 0;

        }

        else {

 

            

            int lheight = height(root.left);

            int rheight = height(root.right);

 

            

            if (lheight > rheight) {

                return (lheight + 1);

            }

            else {

                return (rheight + 1);

            }

        }

    }

 

    

    public virtual IList<int>

    getCurrentLevel(Node root, int level,

                    List<int> currentLevelOrder)

    {

        if (root == null) {

            return currentLevelOrder;

        }

        if (level == 1) {

            currentLevelOrder.Add(root.data);

        }

        else if (level > 1) {

            getCurrentLevel(root.left, level - 1,

                            currentLevelOrder);

            getCurrentLevel(root.right, level - 1,

                            currentLevelOrder);

        }

        return currentLevelOrder;

    }

 

    

    public static void Main(string[] args)

    {

        GFG tree = new GFG();

        tree.root = new Node(1);

        tree.root.left = new Node(0);

        tree.root.right = new Node(1);

 

        tree.root.left.left = new Node(1);

        tree.root.left.right = new Node(0);

 

        tree.root.right.left = new Node(1);

 

        tree.root.left.right.left = new Node(0);

        tree.root.right.left.right = new Node(1);

 

        tree.root.left.right.left.left = new Node(1);

 

        

        List<List<int> > dup_levels

            = tree.printDuplicateLevels(tree.root);

 

        Console.Write("[ ");

        foreach(var curr_level in dup_levels)

        {

            Console.Write("[ ");

            foreach(var dupli_level in curr_level)

            {

                Console.Write(dupli_level + " ");

            }

            Console.Write("] ");

        }

        Console.WriteLine("]");

    }

}

Leave a Comment