How do I get the "depth" of a tree?

Hi,

I'm looking for the node that is the farthest from the "top" of the tree and in particular: how far the distance to the farthest node is? (I continue using the tree in another place, where there is a restriction on how many levels the tree can have, rather than on how many splits there are - which, as I understand it, is what You can limit when building the tree)

In the tree below, the distance would be 7, which is the number of steps between the topmost point on the one hand and either one of the -1 and 1 lowest in the picture.

Does any one know an elegant solution? The tree-object has a lot of information, but I can't figure out how to use it for this objective.

bw, Staffan

Answer 1

[Ilya]

This should work:

function depth = treedepth(tree)

parent = tree.Parent;

depth = 0;
node = parent(end);

while node~=0
    depth = depth + 1;
    node = parent(node);
end

end

[Staffan Sevon]

Fantastic!!!!

It works like we - for some reason say in my country - like a toilet on a train.

Which, surprisingly means that it works like a charm

Many, many thanks to both of You for the help, and in particular to Ilya, Staffan

Answer 2

[Geoff Hayes]

Staffan - how is your tree represented? As a matrix or some sort of list of nodes connected to other nodes? I suspect that you want to create some sort of recursive function that counts the depth of each node (or subtree of the parent tree). For example, if tree is your top-level tree/node, then you could do something like

 maxDepth = getDepth(tree)

where

 function [depth] = getDepth(tree)

 maxDepth = 0;

 for each childNode of tree do

    depthChild = 1 + getDepth(childNode);

    if depthChild > maxDepth
        maxDepth = depthChild;
    end
 end

Note how we recursively check the depth of each child node of the main tree, treating each as if it were a tree itself. We only ever stop recursing when we reach a node without any children.

Answer 3

[Staffan Sevon]

Hi,

thanks for Your answer!

The trees generated by the fitctree function are described as a list of nodes. So, the two primary descriptions are the variables t.Children and t.Parent which in part have "overlapping" information (the variables are shown in the picture below).

The method You propose seems very good, but I can't figure out how to concretize it to fit the information I have. Any additional help/pointers in the right direction that anyone can give, is greatly appreciated

bw, Staffan

<<

<<

>>

>>

[Igor]

I've just check this with a bit of brute-force. And I can confirm it works. It looks like tree nodes are stored in "t.Parent" in a "sorted by depth" manner. Thus only checking the last one is sufficient.

function max_depth = treedepth(tree)
parent = tree.Parent;

max_depth=0;
depthA = NaN([1 numel(parent)]);
for start_node_ind = 1:numel(parent)
    node = parent(start_node_ind);
    depth = 0;
    while node~=0
        depth = depth + 1;
        node = parent(node);
    end
    depthA(start_node_ind) = depth;    
end

max_depth = max(depthA);

% it looks like parents list is stored in a way, that depths are sorted
assert(issorted(depthA));

% thus, the last "parent" is always the deepest
assert(max(depthA)==depthA(end));

end