Can anybody share the algorythm to perform inorder traversal of a binary search tree using parent node(without stack or recursion)
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
Thanks brother for the reply.
What is the meanig of <> ?
NOT EQUAL?
What is the meanig of <> ?
NOT EQUAL?
Yes. = also does double duty as assignment and comparison in that pseudocode syntax.