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

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
0

Thanks brother for the reply.
What is the meanig of <> ?
NOT EQUAL?

0

What is the meanig of <> ?
NOT EQUAL?

Yes. = also does double duty as assignment and comparison in that pseudocode syntax.

This topic has been dead for over six months. Start a new discussion instead.
Have something to contribute to this discussion? Please be thoughtful, detailed and courteous, and be sure to adhere to our posting rules.