Implement a method in Javascript that calculates the level of a tree node

Question

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?

Answer 1

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):

class Node {
    constructor(name, ...children) {
        this.name = name;
        this.children = children;
    }
    getDepth(name) {
        if (this.name == name) return 0;
        for (const child of this.children) {
            const level = child.getDepth(name);
            if (level >= 0) return level + 1;
        }
        return -1; // Not found here
    }
}

// Build the example tree
const root = new Node("root",
    new Node("A",
        new Node("C",
            new Node("G"),
            new Node("H"),
            new Node("I")
        ),
        new Node("D")
    ),
    new Node("B",
        new Node("E"),
        new Node("F")
    )
);

const level = root.getDepth("C");
console.log(level); // 2

You mentioned an opposite method signature in comments, which is also a possibility. Like this:

class Node {
    constructor(name, ...children) {
        this.name = name;
        this.children = children;
    }
    getDepthWithRespectTo(root) {
        if (this === root) return 0;
        for (const parent of root.children) {
            const level = this.getDepthWithRespectTo(parent);
            if (level >= 0) return level + 1;
        }
        return -1; // Not found here
    }
}

// Build the example tree, and keep a reference to node "C"
let node;
const root = new Node("root",
    new Node("A",
        node = new Node("C",
            new Node("G"),
            new Node("H"),
            new Node("I")
        ),
        new Node("D")
    ),
    new Node("B",
        new Node("E"),
        new Node("F")
    )
);

const level = node.getDepthWithRespectTo(root);
console.log(level); // 2