CODEWITHSUNDEEP
javatreebinary-tree
curry_30
curry_30

Reputation: 47

Search for two strings in an unsorted binary tree

I need to show the "path" of the different nodes from a binary tree of strings. The function received two node (begin and end), assuming that they exist in the tree. The tree isn't ordered and cannot be ordered. I've thougt by using the preorder strategy.

For example if the input is monday and month the result should be:

monday party of month

Using the preorder the result is

monday party of friday month

Does anyone know to print the right path?

        family 
      /        \ 
    day        monday 
   /   \       /    \
  zoo  night  party  brother
 /  \  / \    /  \   /  \ 
lion        of   at      club
            /  \
        friday  month

public void fa(NodeArbre inicial,NodeArbre fi){
    if(inicial!=null){
        System.out.println(inicial._contingut+ " _ ");
        fa(inicial._esq,fi);
        fa(inicial._dret,fi);
    }
}

Upvotes: 2

Views: 116

Answers (1)

radoh
radoh

Reputation: 4809

First, you can't println current node, since you don't know if it is on the right path. That means you should rather collect the visited nodes in a list and print it once you reach your target node.

Also I highly doubt that the output you've shown was produced by your program - your program doesn't check for the target node, it traverses the whole child sub-tree.

You could implement this by defining a helper recursive function which would need an additional parameter - list of visited nodes. For example:

public boolean fa(NodeArbre inicial, NodeArbre fi, List<NodeArbre> visited) {
  if (inicial == null)
    return false;
  visited.add(inicial);
  if (inicial == fi || inicial.contingut.equals(fi.contingut)) { // depends on how you want to determine node equality  
    // print list of visited?
    return true;
  }
  if (fa(inicial._esq, fi, visited))
    return true;
  else if (fa(inicial._dret, fi, visited))
    return true;
  visited.remove(inicial);
  return false;
}

Which you'd call from the original method fa

public void fa(NodeArbre inicial, NodeArbre fi) {
  // assign the list to a variable if you want to do something with it...
  // fa will return true if it found the path
  fa(inicial, fi, new LinkedList());
}

Note: I made an assumption that _esq points to the left child and _dret to the right child or vice-versa.

For the non-believers - I have tested it: http://ideone.com/U1sI7t

Upvotes: 1

Related Questions