Searching all nodes of a binary tree in Java

Question

I am trying to write a method to search all nodes of a binary tree for a passed value and return the node when found. I cannot seem to get the logic right to search both sides of the tree. Here is what I have so far.

private Node locate(String p, Node famTree)
{  
    if (root == null)//If tree empty return null;
        return null;
    if (famTree.value.equals(p)) //If leaf contains the passed parent value the boolean becomes true.
        return famTree;
    if (famTree.left != null)
        return locate(p,famTree.left);
    else
        return locate(p,famTree.right);

}

Ted Hopp · Accepted Answer · 2013-04-11T05:21:06.557

9

You are only searching the right subtree when there is no left subtree. You also want to search it when the string was not found in the left subtree. This should do it:

private Node locate(String p, Node famTree)
{
    Node result = null;
    if (famTree == null)
        return null;
    if (famTree.value.equals(p))
        return famTree;
    if (famTree.left != null)
        result = locate(p,famTree.left);
    if (result == null)
        result = locate(p,famTree.right);
    return result;

}

edited Apr 11 '13 at 05:21

answered Apr 11 '13 at 05:16

Ted Hopp

232,168
48
399
521

@TwoMore - I don't just return the result of searching the left subtree whenever it is not `null`. I capture the result of searching the left subtree and search the right subtree if it wasn't found. – Ted Hopp Apr 11 '13 at 05:18
Well but somewhen is your leftsubtree the root and the first if will return null am i right? – CloudyMarble Apr 11 '13 at 05:22
It did work Ted. Thank you. This stumped me all day. I think I was trying to imagine a more complex solution. – BigGrizzle Apr 11 '13 at 05:25
@TwoMore - Um...what? I'm assuming that this is called with `locate("Something", root)`. – Ted Hopp Apr 11 '13 at 05:39
Sorry my mistake, somehow i assumed currentNode is checked for null not root, forget it – CloudyMarble Apr 11 '13 at 05:44
@TedHopp You are right . I have removed my answer and +1 to you. – Geek Apr 11 '13 at 05:53

Searching all nodes of a binary tree in Java

1 Answers1