# Find next occurence in a Tree

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).

-
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

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):
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: