rks rks - 6 months ago 8
Java Question

How can I get my BST add method to add nodes past the first two child nodes?

I'm kinda new to Binary Trees and working on an add method for a simple game. Currently the method replaces the child nodes of the root node every time I add new nodes. How can I get it to add new nodes throughout the tree instead of just replacing the first two child nodes of the root node? This is what I have so far:

public boolean add(User friend) {
User node = friend;
if (root == null) {
root = node;
return true;
}
if (node.key() < root.key()) {
if(root.left == null) {
root.setLeft(node);
}
} else if (node.key() > root.key()) {
if(root.getRight() == null) {
root.setRight(node);
}
}
return true;
}

Answer

Typically, with binary trees you will be writing recursive functions. Instead of managing the insertion from one function call, you can find the side a node belongs to and hand off the insertion to a recursive function call on that node's side.

Assuming that this function belongs to the class User, this should work.

public boolean beFriend(User friend) {
    User node = friend;
    if (root == null) {
        root = node;
        return true;
    }
    if (node.getKey() < root.getKey()) {
        if(root.getLeft() == null) {
            root.setLeft(node);
        } else {
            // recursively call beFriend handing insertion to the child
            root.getLeft().beFriend(node);
        }
    } else if (node.getKey() > root.getKey()) {
        if(root.getRight() == null) {
            root.setRight(node);
        } else {
            // recursively call beFriend handing insertion to the child
            root.getRight().beFriend(node); 
        }
    } else { // node.getKey() == root.getKey() so we replace the previous root
        node.setLeft(root.getLeft());
        node.setRight(root.getRight());
        root = node;
    }
    return true;
}
Comments