2

Right.. so I dont actually know how to title this question but basically I have a node class which I can create children nodes of a parent node (root) but I want to be able to access the lowest node first so the child of the child node and so forth. and work up to the root node (no more functions will be carried out on the root node).

Node Class:

class Node
{
    private string id { get; set; }
    private Node parent { get; set; }
    private List<Node> children { get; set; }
    private string type { get; set; }

    public Node Parent
    {
        get
        {
            return parent;
        }
        set
        {
            parent = value;
        }
    }

    public Node(string id)
    {
        children = new List<Node>();
        this.id = id;
    }

    public Node AddChild(string id)
    {
        children.Add(new Node(id) { Parent = this });
        return children.Last();
    }

    public Node[] AddChildren(string[] children)
    {
        return children.Select(c => AddChild(c)).ToArray();
    }

    public void Flatten(Node node)
    {
        // Create Flatten here
    }
}

This is my attempt at explaining my problem using paint: enter image description here

I forgot to add to the paint image but level 3 in this case is the level that gets the function done on first

if you have any suggestions it would be greatly appreciated and if you need anymore info please ask. I've been searching for an answer the past 2 days and cant seem to find something that will fit my purpose.

Thanks,

Ryan

Liam
  • 27,717
  • 28
  • 128
  • 190
cookies
  • 347
  • 1
  • 6
  • 18
  • 1
    So you are seeking for a [Breadth-first search](https://en.wikipedia.org/wiki/Breadth-first_search) in reverse order. Can you post your `Node` class (at least with properties like `Parent` or `Children` that show the hierarchy)? – Ivan Stoev Oct 24 '16 at 18:03
  • 1
    Must the nodes be traversed in exactly this order, or is it enough that each parent's childrens are fully traversed before the parent itself is visited? – recursive Oct 24 '16 at 18:07
  • @IvanStoev I have added the node class code – cookies Oct 24 '16 at 18:12
  • @recursive yes the node furthest away from the root must be delt with first. Basically before two nodes share a similar parent (converge) – cookies Oct 24 '16 at 18:12
  • 2
    Then reverse post-order DFS will work. It requires less space, see for instance [Using FILO with nested collections](http://stackoverflow.com/questions/40116333/using-filo-with-nested-collections/40116969#40116969). – Ivan Stoev Oct 24 '16 at 18:19
  • Thanks @IvanStoev I will have a look and tell you if I can get anything to work! – cookies Oct 24 '16 at 18:26
  • 1
    They way you've described it, (mathematical operations), can't you just use recursion? Flatten=Operation(childA.Flatten(), childB.Flatten()), where "operation" is whatever function is associated with the current node... I assume you have a node value of some sort, so that you can have a stopping condition for your recursion: if no child nodes just return the current node's value). – johnjps111 Oct 24 '16 at 18:26
  • 2
    Few considerations - is it `binary tree` or `N-ary tree`? Looking at the image above it seems to be a `balanced binary search tree` in which for each node, *value* of all the nodes in *left subtree* is lesser and values of all the nodes in *right sub tree* is greater. This hopefully might give you an hint on *traversal* – L J Oct 24 '16 at 19:02

0 Answers0