Java - Binary Family Tree - Can't Find Node

Question

I'm working on an assignment that requires me to input and display a family tree, by first converting it to a binary tree - child is on the left, and siblings are on the right. I understand trees, traversing trees, and how to search for certain nodes using pre-,in-, and post-order methods.

I've written code to insert a new node, find a node, and print the whole tree, however my findNode method doesn't work properly. I need it to search the tree using pre-order, and return the node it's looking for. Currently, the recursive method makes it all the way to the bottom left (lowest child), and the lowest child's bottom right (lowest sibling), but it never goes back up to the original node I called from - hence breaking recursion.

Here is the code for my FamilyTree and Main classes:

public class FamilyTree
{
Node root;

// Initialize tree
public FamilyTree()
{
    root = null;
}


// --------------------------------------------------------------
// This method inserts a new family member into the tree.
// It takes two parameters - the parent who the new node should
// be inserted under, and the name of the new member being added.
// --------------------------------------------------------------

public void insertNode(String par, String name)
{
    Node parent, current;
    Node newMember = new Node(name);

    // If tree is empty, then the new member becomes the root
    if(root == null)
        root = newMember;


    // If adding a sibling to the root, insert to root's right child
    else if(par == "")
    {
        // Check if root's sibling is empty
        if(root.rightChild == null)
            root.rightChild = newMember;


        // Traverse root's siblings until end, then insert at end
        else
        {
            current = root;

            while(current.rightChild != null)
                current = current.rightChild;

            current.rightChild = newMember;
        }
    }

    else
    {
        // Find the parent where we will insert under
        parent = findNode(par, root);

        System.out.println("parent is = " + parent);
        System.out.println("newMember is = " + newMember + "\n");

        // If that parent doesn't exist, print error msg
        if (parent == null)
            System.out.println("Parent doesn't exist");


        // If parent does exist, but has no left child,
        // then the new member becomes left child
        else if(parent.leftChild == null)   
            parent.leftChild = newMember;


        // If parent already has a left child, then traverse
        // to the end of it's left children and insert node
        else
        {
            current = parent.leftChild;

            while(current.rightChild != null)
                current = current.rightChild;               

            current.rightChild = newMember;
        }   
    }
}


// ------------------------------------------------------------
// This method recursively finds a node in the family tree,
// given the name of the node to look for, and the tree.
// It is run pre-order, and, if found, returns the node
// ------------------------------------------------------------

public Node findNode(String name, Node localTree)
{
    Node current = localTree;

    // Visit the node
    if(current.name == name)
        return current;

    // Pre-order - go left
    if(current.leftChild != null)
    {
        System.out.println("going left to " + current.leftChild);
        return findNode(name, current.leftChild);
    }

    // Pre-order - go right
    if(current.rightChild != null)
    {
        System.out.println("going right to " + current.rightChild);
        return findNode(name, current.rightChild);
    }


    return null;
}

// ------------------------------------------------------------
// This method prints the family tree, given a parent name
// and a tree to print from. It will attempt to find the parent
// node with the given name, then print the entire tree 
// (all children and grandchildren) from that point.
// ------------------------------------------------------------

public void printTree(String par, Node localTree)
{
    Node parent, current;

    // Find the parent to start printing from
    parent = findNode(par, root);
    System.out.println("parent= " + parent);

    // If parent doesn't exist, print error msg
    if (parent == null)
        System.out.println(par + " doesn't exist.");

    else
    {
        current = localTree;

        System.out.println(current);

        if(current.leftChild != null)
            printTree(par, current.leftChild);

        else if(current.rightChild != null)
            printTree(par, current.rightChild);
    }

}

public class Node
{
    Node leftChild, rightChild;
    String name;

    public Node(String n)
    {
        leftChild = null;
        rightChild = null;
        name = n;
    }

    public String toString()
    {
        return name;
    }
}

}

public class Main
{
public static void main (String[] args)
{
    FamilyTree myTree = new FamilyTree();

    myTree.insertNode("", "Grandma Marx");
    myTree.insertNode("", "Great-Aunt Peggie");
    myTree.insertNode("", "Great-Aunt Katherine");
    myTree.insertNode("Grandma Marx", "Aunt Sarah");
    myTree.insertNode("Grandma Marx", "Aunt Tory");
    myTree.insertNode("Grandma Marx", "Uncle Frank");
    myTree.insertNode("Grandma Marx", "Uncle Charles");
    myTree.insertNode("Grandma Marx", "Mom");       

    myTree.insertNode("Aunt Sarah", "Morgan");
    myTree.insertNode("Aunt Sarah", "Tommy");
    myTree.insertNode("Aunt Sarah", "Austin");
    myTree.insertNode("Aunt Sarah", "Luke");

    myTree.insertNode("Aunt Tory", "Tim");

    myTree.insertNode("Mom", "Barret");
    myTree.insertNode("Mom", "Jeremy");
    myTree.insertNode("Mom", "Elliot");


    //myTree.printTree("Grandma Marx", myTree.findNode("Grandma Marx", myTree.root));
}

}

Answer 1

The problem is with your premature return from the search:

public Node findNode(String name, Node localTree)
{
...
    // Pre-order - go left
    if(current.leftChild != null)
    {
        System.out.println("going left to " + current.leftChild);
        return findNode(name, current.leftChild); // <===== HERE!
    }
...
}

This causes the function to end after the left subtree has been traversed, even if the result is null, i.e. no node found.

How about something like this:

public Node findNode(String name, Node localTree)
{
    Node current = localTree;

    // Visit the node
    if(current.name.equals(name))
        return current;

    // Pre-order - go left
    if(current.leftChild != null)
    {
        System.out.println("going left to " + current.leftChild);
        Node nodeFound = findNode(name, current.leftChild);
        if ( nodeFound != null ) {
          // Only return from findNode if we have already found what we're looking for.
          return nodeFound;
        }
    }

    // Pre-order - go right
    if(current.rightChild != null)
    {
        System.out.println("going right to " + current.rightChild);
        return findNode(name, current.rightChild);
    }

    return null;
}

Also, in Java you should never use == to compare Strings. It won't work right. With Strings, always use String.equals(...). See the code above for example, and this SO question.