CODEWITHSUNDEEP
java
user11210084
user11210084

Reputation:

Number of child nodes in a specific level in a non-binary tree

I'm trying to create a method

 public int getNumberOfChildNodes(int level)

which would return a number of child nodes in a specific level. Explanation in the picture below: Level 1 should return 2 (B and C) and level 2 should return 5 (D, E, F, G, H)

I already created a code which returns height of the tree and which returns the number of all child nodes, however I am clueless how to find out the number of childNodes only on specific level. Thanks!

import java.util.*;

public class Tree {

private String name;
private List<Tree> childNodes = new ArrayList<Tree>();

public Tree(String name) {
    this.name = name;
}

public void addChildNode(Tree childNode) {
    childNodes.add(childNode);
}


public int getNumberOfChildNodes() {
    int result = 0;
    for (Tree childNode : childNodes){
        result += childNode.getNumberOfChildNodes();
   }
    return result + childNodes.size();
}

/*

public int getNumberOfChildNodes(int level) {
    int result = 0;        
    for (Tree childNode : childNodes) {
        result += childNode.getNumberOfChildNodes();
 }
    return result + childNodes.size();    }
*/

}

Upvotes: 1

Views: 290

Answers (1)

Omri Attiya
Omri Attiya

Reputation: 4037

Try this recursive function:

public int getNumberOfChildNodes(int level) {
    if(level == 0)
        return childNodes.size();

    int numOfChildren = 0;
    for (Tree childNode : childNodes) {
        numOfChildren += childNode.getNumberOfChildNodes(level-1);
    }

    return numOfChildren ;
}

The idea is to scan each level. And for each recursive call we decrease the level by 1. so when level==0 it means we are in a node at the level we wanted and we will return the size() of this node.

Edit

In this solution I assumed that the level of each node is the distance from the root (i.e root it at level 0 and it's children are at level 1 and so on).

Upvotes: 1

Related Questions