Question 173277 in Javascript Question posted in
A very good W3school tutorial can be found here.

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

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?

Tags:

4

Answers


  1. 0

    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:

    getLevel(){
  let level = 0;
  let parent;
  while(parent = this.parent){
    level++;
  }
  return level;
}

    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 the parent property or accessing the root outside the node’s class which smells bad.

    Login or Signup to reply.
  2. 0

    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
    Login or Signup to reply.
  3. 0

    Since you’re going to iterate the whole tree anyway, it might be easier to precompute depths for all nodes at once:

    function setDepth(node, depth) {
    node.depth = depth
    for (let c of node.children)
        setDepth(c, depth + 1)
}

setDepth(root, 0)

    and then just pick someNode.depth

    Login or Signup to reply.
  4. 0 
        class TreeNode {
      constructor(value) {
        this.value = value;
        this.children = [];
      }
    
      addChild(child) {
        this.children.push(child);
      }
    }
    
    function calculateNodeLevel(root, targetValue) {
      if (root.value === targetValue) {
        return 0; // Found the target node at the root level
      }
    
      for (let child of root.children) {
        const level = calculateNodeLevel(child, targetValue);
        if (level !== -1) {
          return level + 1; // Found the target node in a child subtree
        }
      }
    
      return -1; // Target node not found in the tree
    }
    
    // Example usage:
    const tree = new TreeNode(1);
    const child1 = new TreeNode(2);
    const child2 = new TreeNode(3);
    const grandchild = new TreeNode(4);
    child2.addChild(grandchild);
    tree.addChild(child1);
    tree.addChild(child2);
    
    console.log(calculateNodeLevel(tree, 1)); // Output: 0
    console.log(calculateNodeLevel(tree, 2)); // Output: 1
    console.log(calculateNodeLevel(tree, 3)); // Output: 1
    console.log(calculateNodeLevel(tree, 4)); // Output: 2
    console.log(calculateNodeLevel(tree, 5)); // Output: -1 (Node not found)

In this example, the TreeNode class represents a node in the tree, and it has a value property to store the value of the node and a children array to store its child nodes.

The calculateNodeLevel function takes a root node and a targetValue as input. It recursively traverses the tree starting from the root and checks if the value of each node matches the targetValue. If a match is found, it returns the level of that node (0 for the root level, 1 for its children, and so on). If the targetValue is not found in the tree, it returns -1.

In the example usage section, a simple tree is created, and the calculateNodeLevel function is called with different target values to demonstrate its usage and output.
    Login or Signup to reply.
Please signup or login to give your own answer.

Back To Top
Search