Traversing a complex tree structure

Question

I have a tree structure like this:

A (20,40)
    B (21,22)
    C (23,33)
        D (24,29)
            E (25,26)
            F (27,28)
        G (30,31)
        H (32,33)
    I (34,37)
        J(35,36)
    K (38,39)

The levels can be however deep so I need to use recursion. How do I find the children of a given node and their level values (eg. 'B' would be level 2)?

I am quite stuck with this problem but my pseudo-code so far is roughly this:

Pass in a node --> if the difference between its left value and its right value is > 1, find the next child by using left value + 1

Answer 1

There are many ways to do this! Take a look at Tree traversal for ideas.

From you're example it looks like you have some ranges on each node that you should use.

Just for the fun I have tried to (very fast) construct some code - again this is done with no knowleged about what parameters you use in the search. Please note that this is only an example, constructed very fast:

A node structure

class Node
{
    public int Min { get; set; }
    public int Max { get; set; }

    public List<Node> Children { get; set; }

    public Node(int min, int max)
    {
        this.Min = min;
        this.Max = max;
        this.Children = new List<Node>();
    }

    public void Add(Node child)
    {
        this.Children.Add(child);
    }
}

A main class

The class contains a function for building the tree (not pretty), and a function that is recursive, and returns the leve, and outputs the node object.

class Program
{
    static void Main(string[] args)
    {
        var tree = GetTree();
        Node node;
        var val = Find(tree, 21, 1, out node);

        Console.WriteLine("depth: {0}", val);
        Console.WriteLine("\t{0}, {1}", node.Min, node.Max);
        Console.ReadKey();
    }

    private static int Find(Node curNode, int value, int level, out Node foundNode)
    {
        foundNode = curNode;
        foreach (var child in curNode.Children)
        {
            if (child.Min <= value && child.Max >= value)
                return Find(child, value, level + 1, out foundNode);
        }
        return level;
    }

    private static Node GetTree()
    {
        var a = new Node(20, 40);
        var b = new Node(21, 22);
        var c = new Node(23, 33);
        var d = new Node(24, 29);
        var e = new Node(25, 26);
        var f = new Node(27, 28);
        var g = new Node(30, 31);
        var h = new Node(32, 33);
        var i = new Node(34, 37);
        var j = new Node(35, 36);
        var k = new Node(38, 39);

        d.Add(e);
        d.Add(f);

        c.Add(d);
        c.Add(g);
        c.Add(h);

        i.Add(j);

        a.Add(b);
        a.Add(c);
        a.Add(i);
        a.Add(k);

        return a;
    }
}

private static Node GetTree()
{
    var a = new Node(20, 40);
    var b = new Node(21, 22);
    var c = new Node(23, 33);
    var d = new Node(24, 29);
    var e = new Node(25, 26);
    var f = new Node(27, 28);
    var g = new Node(30, 31);
    var h = new Node(32, 33);
    var i = new Node(34, 37);
    var j = new Node(35, 36);
    var k = new Node(38, 39);

    d.Add(e);
    d.Add(f);

    c.Add(d);
    c.Add(g);
    c.Add(h);

    i.Add(j);

    a.Add(b);
    a.Add(c);
    a.Add(i);
    a.Add(k);

    return a;
}

Answer 2

You can always use regular expressions, right? :)

You can do global match for this:

([    ]+)([A-Z]+) \(\d+,\d+\)

and count how many times the four spaces are repeated, which is basically the level of the letter.

If you want to store the actual tree, you have to also keep record of the parent node.