HiveBrain v1.2.0
Get Started
← Back to all entries
patternjavaMinor

List creation of BST's nodes

Submitted by: @import:stackexchange-codereview··
0
Viewed 0 times
listnodescreationbst

Problem

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> getNodesPerDepth(BinaryNode root){   
     if(root == null) {   
         throw new IllegalArgumentException();  
     }   
     List> result = new LinkedList>();  
     result.add(new LinkedList());   
     getNodesPerDepth(result, root, 0);   
     return result;  
}  

private void getNodesPerDepth(List> lists, BinaryNode root , int depth){    
      if(root == null){  
        return;  
      }   
      lists.get(depth).add(root);   
      if(lists.size() ());  
      }    
      getNodesPerDepth(lists, root.left, depth + 1);   
      getNodesPerDepth(lists, root.right, depth + 1);  
}

Solution

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;
}

Code Snippets

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;
}

Context

StackExchange Code Review Q#12127, answer score: 2

Revisions (0)

No revisions yet.