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

35 views (last 30 days)
Staffan Sevon
Staffan Sevon on 7 May 2015
Commented: Igor on 12 Jul 2017
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

Accepted Answer

Ilya
Ilya on 8 May 2015
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
  1 Comment
Staffan Sevon
Staffan Sevon on 8 May 2015
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

Sign in to comment.

More Answers (2)

Geoff Hayes
Geoff Hayes on 7 May 2015
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.

Staffan Sevon
Staffan Sevon on 8 May 2015
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
<<
<<
>>
>>
  1 Comment
Igor
Igor on 12 Jul 2017
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

Sign in to comment.

Products

Community Treasure Hunt

Find the treasures in MATLAB Central and discover how the community can help you!

Start Hunting!