CODEWITHSUNDEEP
java
user1235720
user1235720

Reputation:

Searching a Binary Tree for a String

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.

Upvotes: 0

Views: 3984

Answers (1)

Vincent Mimoun-Prat
Vincent Mimoun-Prat

Reputation: 28541

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
}

Upvotes: 1

Related Questions