Given a tree such as the following – please note this is NOT a binary tree:
root
/
A B
/ /
C D E F
/
G H I
I would like to write a method, which returns the level of the node I call the method on. For example, when calling C.getLevel()
I am expecting the return value 2, assuming the level of the root node is 0.
Each node has but two properties: a name and an array of its direct children.
Since I am working with a tree here, I have a feeling I need to solve this issue recursively. So, in a first step, I have to figure out an exit condition – when is my method going to return? Most likely when there are no children.
I don’t really have a good approach for this issue, but just to give us something to work with, I’ll post a start method:
getLevel(level = 0) {
if (this.children.length === 0) {
return level;
}
for (let child of this.children) {
level = child.getLevel(level + 1);
}
}
Can somebody help me figure this out?
4
Answers
You cannot have such method because you don’t have a reference to the parent element in a node. Basically the level is the number of parent nodes.
And that’s btw is a common unbalanced tree design.
So I would suggest to follow the common design and add
parent
property to nodes.If you would have
parent
the level obtaining is trivial:Also this could be solved if we could access the root node, but I think it’s not efficient as having the parent node property in a node.
If you prepare your tree in JS code I would bother to traverse the tree from the root element and find a node’s level (if the reference to root is allowed to use). But again that would imply the
root
property of a node which is worse than having theparent
property or accessing the root outside the node’s class which smells bad.You need to start the search from the root and then look to find the node. This could either be based on a node instance that is given as argument, or on a name that the target node has ("C" in the example).
Note that I prefer to call this aspect depth instead of level — but it’s the same thing.
Here is an implementation that searches for the node by name, starting at the root (I named the method
getDepth
):You mentioned an opposite method signature in comments, which is also a possibility. Like this:
Since you’re going to iterate the whole tree anyway, it might be easier to precompute depths for all nodes at once:
and then just pick
someNode.depth