patternjavaMinor
List creation of BST's nodes
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:
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.