Searching a Binary Tree for a String

Question

I am looking to search a binary tree to find a string stored in the nodes.

public void traverse (BinaryTreeNode root){ 
    if (root.leftchild != null){
        traverse (root.leftchild);
    }
        System.out.println(root.character);
    if (root.rightchild != null){
        traverse (root.rightchild);
    }
}

This works perfectly fine and displays all the nodes in the tree. (The code was worked from code on another old stackoverflow question! My issue is how to compare root.character to the inputted string and if it matches break out of the recursion. If someone could drop some hints I would appreciate it.

    public BinaryTreeNode traverse (BinaryTreeNode root, String inString){ // Each child of a tree is a root of its subtree.
    if (root.character != null) {
        if (root.character.equalsIgnoreCase(inString)) {
            System.out.println("root.charcter: " + root.character + " char " + inString);
            return root;
        }
    }
    if (root.leftchild != null){
        traverse (root.leftchild, inString);
    }

    if (root.rightchild != null){
        traverse (root.rightchild, inString);
    }

    return null;
}

The code above seems to work, it returns the correct BinaryTreeNode however, I haven't worked out how to stop the recursion once the node is found and therefore it returns a null at the end aswell.

Vincent Mimoun-Prat · Accepted Answer · 2012-11-21 21:17:38Z

1

You are calling the traverse function without passing it the string to search... You are also missing return value in lots of cases.

You need to think a bit more about when your function should terminate the recursion (in that case, return the node) and what the function should do when not terminating but exploring the rest of the tree.

e.g. in pseudo code (you do the programming):

findNode(root, query) {
  // nothing to search, not found
  if root==null return null  

  // Found it!
  if root.name==query return root

  // This is when we recurse left, stop if we found a result
  leftResult = findNode(root.left, query)
  if leftResult!=null return leftResult

  // else try to the right, stop if we found a result
  rightResult = findNode(root.right, query)
  if rightResult!=null return rightResult

  // Nothing else to try, not found
  return null
}

edited Nov 21, 2012 at 21:17

answered Nov 21, 2012 at 21:10

Vincent Mimoun-Prat

28.6k16 gold badges85 silver badges126 bronze badges

Sign up to request clarification or add additional context in comments.

3 Comments

Cornelius Dol Over a year ago

And don't use string==otherString in Java, use string.equals(otherString).

Vincent Mimoun-Prat Over a year ago

Yes, that's pseudo code, come back with your implementation and ask for advice if it does not work.

user1235720 Over a year ago

Thank you for the sudo code. I have updated the code. I have updated the code in my original question to what I have at the moment. It works and returns the correct node, but there is no way to stop the recursion in the code and therefore it returns NULL as well at the end.

Collectives™ on Stack Overflow

Searching a Binary Tree for a String

1 Answer 1

3 Comments

Your Answer

Hot Network Questions

Collectives™ on Stack Overflow

1 Answer 1

3 Comments

Your Answer

Sign up or log in

Post as a guest

Related