3
\$\begingroup\$

I want to create lists of the nodes of a binary tree at each depth.
So if the depth is X I would have X lists.
Please see my approach. I think it is correct. Am I right to believe it is correct? Any input is welcome:

public List<List<BinaryNode>> getNodesPerDepth(BinaryNode root){   
     if(root == null) {   
         throw new IllegalArgumentException();  
     }   
     List<LinkedList<BinaryNode>> result = new LinkedList<LinkedList<BinaryNode>>();  
     result.add(new LinkedList<BinaryNode>());   
     getNodesPerDepth(result, root, 0);   
     return result;  
}  

private void getNodesPerDepth(List<LinkedList<BinaryNode>> lists, BinaryNode root , int depth){    
      if(root == null){  
        return;  
      }   
      lists.get(depth).add(root);   
      if(lists.size() < depth + 1 && (root.left != null || root.right != null)){   
           lists.add(new LinkedList<BinaryNode>());  
      }    
      getNodesPerDepth(lists, root.left, depth + 1);   
      getNodesPerDepth(lists, root.right, depth + 1);  
}   
\$\endgroup\$
2
\$\begingroup\$

Do you really want to go recursive on this? Binary trees in the worst case may be a linear list. A better idea is to do some thing like this:

getNodesPerDepth(rootNode) {
    list.add(rootNode); // Start with the root node,
    dlst = new List() // depth lit
    while(list.size() != 0) {
        nextlst = new List(); // make a list of children to iterate next phase.
        for(e : list) {
          for (c : e.children())
             nextlst.add(c);
        }
        dlst.add(list);
        list = nextlst;
    }
    return dlst;
}
\$\endgroup\$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.