How to find the leaf-only parent nodes in an n-ary tree

Question

I'm trying to solve the following algorithm:

You have an n-ary tree. Find all the nodes satisfying the following condition:

• the node has child node(s) but all of the child nodes are leafs (they have no children ). Return a list of leaf only parent nodes and their depth in the tree.

So if I have the tree below, the only node satisfying the above condition is D, because it has descendants (E) but they don't have children.

  I am root!
     /\ \
    A B  F
      /\
     C  D
         \
         E

I'm trying to implement this in Java but pseudocode will also work for me. I have the tree and node structures implemented here: N-ary trees in Java.

All I need is the algorithm.

Answer 1

1. start at root
2. while left son exists : go to left son
3. go back to father and check next son
4. if has no other sons : insert father to list
5. else insert father to list and go to step 2 but keep a depth counter and if found grandchildren : remove father from list

6. if finished all nodes : return list

   root / \ \ A B F / \ C D \ E

run example:

• go to A
• go back to root and insert root to list
• go to B
• go to C (remove root from potential because of counter)
• go back to B and add B to list
• go to D
• go to E (remove B from potential because of counter)
• go back to D and insert to list
• go back to B
• go back to root
• go to F (don't insert root because root was already inserted [and removed]
• return list which has only D

To make this work you should have a counter running for the node you are checking (to see if grandchildren exist) and also you should have a way of knowing if a node has been removed from the list so you would not insert it again (I didn't explicitly write it but I used 2 list - 1 for potentials and 1 for final)

Answer 2

OK, I got it. Here's the solution I've reached. I'm sure there are better solutions though - you're welcome to correct me.

// kick off the recursion
public Map<Integer, Integer> findLeafOnlyParents(GenericTree<Integer> tree){
        Map<Integer, Integer> resultMap = new HashMap<>();

    // start search from the root
        traverseWithDepth(tree.getRoot(), resultMap, 0);

        return resultMap;
    } 


private void traverseWithDepth(GenericTreeNode<Integer> node,  Map<Integer, Integer> traversalResult, int depth) {

  // check if the current note in the traversal is parent Of leaf-only nodes
  if (isParentOfLeafOnly(node)){
    traversalResult.put(node.data, depth);
  }

  // check the node's children
  for(GenericTreeNode<Integer> child : node.getChildren()) {
    traverseWithDepth(child, traversalResult, depth + 1);
  }

}

// the main logic is here
private boolean isParentOfLeafOnly(GenericTreeNode<Integer> node){
  boolean isParentOfLeafOnly = false;

  // check if the node has children
  if(node.getChildren().size() > 0){

    // check the children of the node - they should not have children
    List<GenericTreeNode<Integer>> children = node.getChildren();
    boolean grandChildrenExist = false; 

    // for each child check if it has children of its own
    for(GenericTreeNode<Integer> child : children) {
      grandChildrenExist = child.getChildren().size() > 0;

      // once found note that the current node has grandchildren,
      // so we don't need to check the rest of the children of the node
      if (grandChildrenExist){
        break;
      }
     }

     // we need only the parents who don't have great children
    isParentOfLeafOnly = !grandChildrenExist;
  }
  return isParentOfLeafOnly;
}