How to efficiently build a tree from a flat structure?

by

Store IDs of the objects in a hash table mapping to the specific object. Enumerate through all the objects and find their parent if it exists and update its parent pointer accordingly.

class MyObject
{ // The actual object
    public int ParentID { get; set; }
    public int ID { get; set; }
}

class Node
{
    public List<Node> Children = new List<Node>();
    public Node Parent { get; set; }
    public MyObject AssociatedObject { get; set; }
}

IEnumerable<Node> BuildTreeAndGetRoots(List<MyObject> actualObjects)
{
    Dictionary<int, Node> lookup = new Dictionary<int, Node>();
    actualObjects.ForEach(x => lookup.Add(x.ID, new Node { AssociatedObject = x }));
    foreach (var item in lookup.Values) {
        Node proposedParent;
        if (lookup.TryGetValue(item.AssociatedObject.ParentID, out proposedParent)) {
            item.Parent = proposedParent;
            proposedParent.Children.Add(item);
        }
    }
    return lookup.Values.Where(x => x.Parent == null);
}

More Related Contents:

  1. Iterating over a Binary Tree with O(1) Auxiliary Space
  2. reconstructing a tree from its preorder and postorder lists
  3. How can I pair socks from a pile efficiently?
  4. Unique (non-repeating) random numbers in O(1)?
  5. Graph Algorithm To Find All Connections Between Two Arbitrary Vertices
  6. How do you detect Credit card type based on number?
  7. What distribution do you get from this broken random shuffle?
  8. Is there an O(n) integer sorting algorithm?
  9. Determine font color based on background color
  10. Nearest neighbors in high-dimensional data?
  11. What algorithm gives suggestions in a spell checker?
  12. How can I measure the similarity between two images? [closed]
  13. Generate all unique substrings for given string
  14. Non-recursive depth first search algorithm [closed]
  15. Need help in mod 1000000007 questions
  16. Sum-subset with a fixed subset size
  17. What is a good Hash Function?
  18. Binary Search in Array
  19. Calculate largest inscribed rectangle in a rotated rectangle
  20. The Sieve of Atkin
  21. How to partition an array of integers in a way that minimizes the maximum of the sum of each partition?
  22. 3 dimensional bin packing algorithms
  23. Find 2 numbers in an unsorted array equal to a given sum
  24. Algorithm to find the most common substrings in a string
  25. In Order Successor in Binary Search Tree
  26. Optimizing Conway’s ‘Game of Life’
  27. “Rounding” colour values to the nearest of a small set of colours
  28. How do I find the Excel column name that corresponds to a given integer? [duplicate]
  29. Iterative tree walking
  30. Memory efficient power set algorithm

Leave a Comment