Can anybody share the algorythm to perform inorder traversal of a binary search tree using parent node(without stack or recursion)

3
Contributors
4
Replies
5
Views
5 Years
Discussion Span
Last Post by deceptikon

What does the tree look like?

What does the tree look like?

Why should that matter? As long as it's a valid binary search tree, the algorithm won't change depending on how the tree looks.

Can anybody share the algorythm to perform inorder traversal of a binary search tree using parent node(without stack or recursion)

As long as you save the encountered node, it's a relatively simple matter of using the value of the previous node to determine where to go next. For example (pseudocode):

``````while it <> null
if prev = it.parent
prev = it

if it.left <> null
it = it.left
else
visit(it)

if it.right <> null
it = it.right
else
it = it.parent
endif
else if prev == it.left
prev = it
visit(it)

if it.right <> null
it = it.right
else
it = it.parent
else if prev = it.right
prev = it
it = it.parent
endif
endwhile
``````