Depth of n-ary tree

S

Stefan Poehn

Wynan James said:
How do I find the depth of a n-ary tree?

depends on the data structure you are using.
Use Depth First Search or Breadth First Search,
if you are not using a variable that counts the depth
while you are adding nodes to this tree or deleting
nodes from this tree or changing the parent/child links.

Regards
Stefan
 
W

Wynan James

Im using breadth first search and Im traversing the tree. I wont be
adding/deleting nodes. Will calling node.getFirstChild() recursively do the
trick? It might fail on textnodes I think..then how do I pick up and carry
on?
 
S

Stefan Poehn

Wynan James said:
Im using breadth first search and Im traversing the tree. I wont be
adding/deleting nodes. Will calling node.getFirstChild() recursively do the
trick? It might fail on textnodes I think..then how do I pick up and carry
on?

you can write a recursive method
int getMaxDepthInSubtree() {
if (thisNode is leaf) {
return 1; // or 0, check the definition of "depth"
} else {
maxDepth = max of getMaxDepthInSubtree over all children
return maxDepth + 1;
}
}

You have to traverse the whole tree, so you have
a complexity of O(n) (n= number of nodes in the tree)

HTH
Stefan

P.S: what is a textnode?
 
W

Wynan James

Thanks. I will use this..a text node(my term) for lack of a better word is a
node of name #text
 
S

Stefan Poehn

Sajjad Lateef said:
You could keep track of the max depth as you add nodes.
That's easier than a full depth-first search.

It is not that easy. If you delete a node you must decrease
the tree depth if and only if this node is on a path that is longer
than all other paths from the root to a leaf and therefore you
have to make a DFS/BFS again.

Regards
Stefan
 
B

Brian Palmer

Stefan Poehn said:
It is not that easy. If you delete a node you must decrease
the tree depth if and only if this node is on a path that is longer
than all other paths from the root to a leaf and therefore you
have to make a DFS/BFS again.

You should be able to do this simply by labelling each node with the
maximum depth of the subtree rooted at that node; inserting or
deleting a node then just requires you to walk back up to the root,
updating the labels. (So time roughly 'inserting/deleting +
O(maxdepth)' where 'maxdepth' is the previous maximum depth, depending
on specifics such as whether this is a balanced n-ary tree and whether
non-leaf nodes can be inserted/deleted).
 
S

Sajjad Lateef

It is not that easy. If you delete a node you must decrease
the tree depth if and only if this node is on a path that is longer
than all other paths from the root to a leaf and therefore you
have to make a DFS/BFS again.

You are correct. I forgot the deletion case.

Another solution: A separate array for number of elements at
each level can be maintained (the index is the depth)

As elements are added, the value at that index is incremented.
As elements are removed, the value at that index is decremented.

Traversing this array may be cheaper, i.e. O(1), than a DFS or BFS.
 
S

Stefan Poehn

Brian Palmer said:
You should be able to do this simply by labelling each node with the
maximum depth of the subtree rooted at that node; inserting or
deleting a node then just requires you to walk back up to the root,
updating the labels. (So time roughly 'inserting/deleting +
O(maxdepth)' where 'maxdepth' is the previous maximum depth, depending
on specifics such as whether this is a balanced n-ary tree and whether
non-leaf nodes can be inserted/deleted).

Thank you, this is the elegant solution. I will use it next time
when I am coding algorithms on trees :)

Stefan
 

Ask a Question

Want to reply to this thread or ask your own question?

You'll need to choose a username for the site, which only take a couple of moments. After that, you can post your question and our members will help you out.

Ask a Question

Members online

No members online now.

Forum statistics

Threads
473,744
Messages
2,569,483
Members
44,903
Latest member
orderPeak8CBDGummies

Latest Threads

Top