CODEWITHSUNDEEP
c++algorithmtreetrie
ValentaTomas
ValentaTomas

Reputation: 270

How to know that I'm at the end of tree when iterating?

I'm writing (inorder) iterator for tree structure (left child pointer, right child pointer, parent pointer) and I'm stuck, because I can't think of a way to stop iterating when I've already visited all nodes. How can I check if the node I'm currently at is the last node of tree?

EDIT

The tree structure here is supposed to be binary trie, I need inorder traversal to achieve lexicological order of node "keys" and I have the recursive version already done - I'm trying to do the iterative version, because a lot of other functions traversing the tree and I'm not really sure how to write the recursive version generic enough to support all the uses.

I'm sorry if my initial question was non-accurate, downvote as you see fit.

Upvotes: 0

Views: 1524

Answers (2)

paxdiablo
paxdiablo

Reputation: 881103

If you're doing it recursively, this is inherent in the algorithm, you don't need to manually check, as per the following pseudo-code:

def processTree(node):
    if node == null: return
    processTree(node.left)
    print(node.value)
    processTree(node.right)

processTree(rootNode)

Consider the point where you process the very last node, say 7 in the following tree:

    __1__
   /     \
  2       3
 / \     / \
4   5   6   7

At that point, you will have already processed everything to the left and all parents so you will simply step up the tree and exit.

Upvotes: 2

drbombe
drbombe

Reputation: 639

One approach is to calculate the total of nodes before searching the tree, say N. Then you can use a size_t counter to count it, i.e. pass the reference of the counter into the recursive call to for tree search, and do a ++counter at each final node.

Upvotes: -1

Related Questions