CODEWITHSUNDEEP
javatreebreadth-first-search
snackerMaker
snackerMaker

Reputation: 11

BFS on a tree with lists

So I'm building this tree which has 1..* Nodes where each node has a list which in themselves can have 1..* nodes.

The first three levels of the tree I can build just fine but then it won't work more if I don't code all the levels which are just plain stupid. The solution is of course to use some kind of recursive method and a BFS.

Basically, in my TreeBuilder class, I want to be able to call tree.getNodesAtDepth(depth)) and get a list of all nodes that are at that depth. Problem is that I don't understand how I can implement the getNodesAtDepth(depth) method.

All the examples I find are for binary trees. An alternative is to have the addChild method take a depth argument so I can specify at which depth to insert the child at.

In the end, this is what I want: I have a tree with a root. The root has a list which has 4 children nodes. I want to get the 4 children. For each child generate three nodes. So for child 0 has 3 children, child 1 has 3 children, child 3 has 3 children and child 4 has 3 children. And so forth

Maybe a possible soultion is to have a level attribute on each node and search for that node and then return it's parent. Beacuse it's parent should have a list of all the nodes at the searched for node.

Upvotes: 1

Views: 567

Answers (2)

mjlowky
mjlowky

Reputation: 1223

If I assume your class tree structure is : 

class Tree {
    List<Tree> children
    ...
}

Then you can recursively iterate through the tree until you find the expected depth: 

void recursivelyCollectNodesAtDepth(int depth,
                                    List<Tree> nodesAtDepth,
                                    Tree tree,
                                    int currentDepth) {

    if (tree == null) {
        return;
    }

    if (depth == 0) {
        nodesAtDepth.add(tree);
    } else if (currentDepth + 1 == depth) {
        // add children to the node list when expected depth is reached
        if (tree.getChildren() != null) {
            nodesAtDepth.addAll(tree.getChildren());
        }
    } else if (currentDepth < depth) {
        // iterate and recursively travers through child nodes
        for (Tree childTree : tree.getChildren()) {
            recursivelyCollectNodesAtDepth(depth,
                    nodesAtDepth,
                    childTree,
                    currentDepth + 1);
        }
    }
}

Here the tree nodes a recursively traversed to the expected level

Upvotes: 0

Schidu Luca
Schidu Luca

Reputation: 3947

Try this method :

static void getNodesAtDepth(Node root, int currentLevel, int level, List<Node> nodes) {
    if(root == null) return;
    if(level == 0) {
        nodes.add(root);
        return;
    }

    if(currentLevel + 1 == level) {
        if(root.getNodeList() != null) {
            nodes.addAll(root.getNodeList());
        }
    }

    if(currentLevel < level) {
        if(root.getNodeList() != null) {
            for(Node node : root.getNodeList()) {
                getNodesAtDepth(node, currentLevel + 1,  level , nodes);
            }
        }
    }
}

How to use it :

List<Node> nodeList = new LinkedList<>();
getNodesAtDepth(root, 0, 2, nodeList);

root of course is the root of your tree. nodeList will store all your nodes at desired level (in my case it's 2). Second parameter is always 0, (that's for keeping track of the current level)

Upvotes: 0

Related Questions