Take the 2-minute tour ×
Programmers Stack Exchange is a question and answer site for professional programmers interested in conceptual questions about software development. It's 100% free, no registration required.

Have a tree of variable depth, and width. What is the best algorithm to find the next occurence of the node in that tree.

Next = Search to the right side of the tree ( as in breadth first search )

The selection criteria for the next occurrence of the tree is changeable in different situations.

For example, at one place, I want find the next occurrence of the node that contains the Value equal to the current node.

In another, I want to select the next value that is less than the current value.

Once the next Occurrence is found, the program can terminate and return the value or node.

          5
     6           9
 10  7  0      5 6 8
5  6   9 5

Suppose I've a pointer to node (depth = 4, value = 5, parent = 10)... when I perform the search I want to get the pointer to the node (depth = 4, value =5, parent=0).

Say this is not there, then I want to get node(depth =1, value=5, rootNode).

share|improve this question
    
Are you just finding the first occurrence in a subtree? –  S.Lott Jul 1 '11 at 19:42
    
not in a subtree alone. Hmm to be clear, it is like a depth first search, in nextsiblings, and then if not found, in it's parent's nextsiblings. and so on. –  Boopathi Rajaa Jul 1 '11 at 20:36
    
Good Q, but this needs to be moved to SO. –  Job Jul 2 '11 at 3:23

1 Answer 1

up vote 2 down vote accepted

You want a modified depth-first search. The modification is that it has to have code to figure out where it is in the search, and then proceed from there.

Let's assume that each node has a parent and children. Then you want to do something like this:

def find_next_in_tree(node, relation):
    answer = do_depth_first_search(node, relation)
    if answer:
        return answer
    while node.parent:
        old_node = node
        node = node.parent
        children = node.children

        # Find where node is in children.
        i = 0
        while i < children.length:
            if old_node == children[i]:
                break
            i += 1

        # Search remaining children
        i += 1
        while i < children.length:
            answer = do_depth_first_search(children[i], relation)
            if answer:
                return answer
            i += 1
    return None
share|improve this answer

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.