After major reformatting work, I have refactored your code into a much more legible form. While substantially different, the following is logically identical to your code:
private Node<K, V> getNode(K key, ArrayList<Node<K, V>> children){
if (children == null) return null;
if (root.getKey().equals(key)) return root;
for (Node<K,V> child : children) {
if (child.getKey().equals(key)) return child;
getNode(key, child.getChildren());
}
return null;
}
Now, we can pick apart the code and fix it.
The first problem is that you don't have a javadoc comment in front of the method documenting its parameters and return value with @param
and @return
. That is someting you need to fix.
Second off, this method should be implemented as a class method of the Node
class, and should be public
. That is:
class Node<K,V> {
// ... whatever else this class has in it ...
public K getKey() { /* ... stuff ... */ }
ArrayList<Node<K,V>> children = new ArrayList<>();
public Node<K, V> getNode(K key){
if (children == null) return null;
if (key.equals(this.getKey())) return this;
for (Node<K,V> child : children) {
if (child.getKey().equals(key)) return child;
child.getNode(key);
}
return null;
}
}
Also, since we have now guaranteed that children
always gets initialized, and is entirely under our control, we can get rid of the bogus null
check.
public Node<K, V> getNode(K key){
if (key.equals(this.getKey())) return this;
for (Node<K,V> child : children) {
if (child.getKey().equals(key)) return child;
child.getNode(key);
}
return null;
}
Now, you are redundantly checking the children. Since getNode()
already checks if this
is the correct node, there is no reason to separately check each child of the current node:
public Node<K, V> getNode(K key){
if (key.equals(this.getKey())) return this;
for (Node<K,V> child : children)
child.getNode(key);
return null;
}
Now that we have gotten rid of this much code, it should be fairly obvious what the problem actually is: the upper method never actually does anything with the node turned up by searching the child. A simple change is enough to fix this though:
public Node<K, V> getNode(K key){
if (key.equals(this.getKey())) return this;
for (Node<K,V> child : children){
Node<K,V> result = child.getNode(key);
if(result != null) return result;
}
return null;
}
Note that we should not be checking if the child is null
. This should be handled by the method we expose for adding new values, and we should never be adding foreign nodes to our tree:
public boolean put(K key, V value){
children.add(new Node<>(key, value));
}
And one more thing: There is no need for a seperate Tree
class at all! You should not have one, all its functionality should exist entirely within the node class. Ideally, the root node is the tree.