Search for two strings in an unsorted binary tree

Question

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);
    }
}

Can you only traverse down the tree, or can you go through parents as well (like from monday to lion)? — callyalater
– callyalater, Commented Mar 1, 2016 at 18:10
Okay. Then I would think of this problem as a directed graph and use Dijkstra's Algorithm or Kruskal's to traverse it. — callyalater
– callyalater, Commented Mar 1, 2016 at 18:14

radoh · Accepted Answer · 2016-03-01 19:38:40Z

1

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

edited Mar 1, 2016 at 19:38

answered Mar 1, 2016 at 18:37

radoh

4,8555 gold badges34 silver badges50 bronze badges

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

4 Comments

radoh Over a year ago

@gpasch Why would both children be add to visited? I remove the child in an incorrect path. And if already one child was on the right path, I don't check the other one.

callyalater Over a year ago

Double equals (==) always scares me in comparisons in Java. Do you think it would be better to call the equals() method?

radoh Over a year ago

@callyalater no, because that's exactly what I want - to check if the instances are the same. Of course, it depends on how OP uses the function - if he creates a new instance of NodeArbre and considers them to be equal when their _contingut fields are equal, then it would be a good idea to compare those fields instead.

radoh Over a year ago

@gpasch I have added a link to ideone example.

Collectives™ on Stack Overflow

Search for two strings in an unsorted binary tree

1 Answer 1

4 Comments

Your Answer

Hot Network Questions

Collectives™ on Stack Overflow

1 Answer 1

4 Comments

Your Answer

Sign up or log in

Post as a guest

Related