W
Wynan James
How do I find the depth of a n-ary tree?
Wynan James said:How do I find the depth of a n-ary tree?
How do I find the depth of a n-ary tree?
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?
Sajjad Lateef said:You could keep track of the max depth as you add nodes.
That's easier than a full depth-first search.
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.
How do I find the depth of a n-ary tree?
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.
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).
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.