Adding (and Finding) an element to a binary tree (NOT BST)

Question

So I'm trying to put an element in a binary tree (not a search tree) in java. I looked everywhere, and all I can see are algorithms for inserting it into a binary search tree (and I want a simple binary tree). Given the value of the parent node, I need to set the left and right children. My plan looks like this:

public void addLeft(E elem, E parentVal) {
//Find node with parentVal
//Create node with element elem (call it newNode)
//Set the left child of the node with parentVal as newNode
}

The last 2 steps are fairly simple, so my real problem is finding the node with a given value. In a search tree, it is an easy task, but in a normal binary tree, I don't know how to do it. I understand that it won't be efficient; as far as I know, to add an element to a given node in a normal binary tree, we have to traverse the entire tree to find that node. Any suggestions on how to do this? Assume there will be no repeats of numbers (all nodes have a unique element). I've tagged this as algorithm/pseudocode, so just a basic idea is all I need to get started (although code is appreciated as well).

Answer 1

Here is a simple way of recursively traversing the tree and stopping when parentVal is found:

// returns true if the element has been added to this subtree
public boolean addLeft(E elem, E parentVal) {
    if (this.equals(parentVal)) {
        //Create node with element elem (call it newNode)
        //Set the left child of the node with parentVal as newNode
        return true;
    } else if (leftChild != null && leftChild.addLeft(elem, parentVal)) {
        return true;
    } else {
        return rightChild != null && rightChild.addLeft(elem, parentVal);
    }
}

This is assuming that a node has access to its children through leftChild / rightChild.