Logo Questions Linux Laravel Mysql Ubuntu Git Menu
 

How to do in-order traversal of a BST without recursion or stack but using parent pointers?

Is it possible to do an iterative in-order-traversal on a BST whose node has a parent pointer (the parent of the root is null) without using a visited flag or a stack?

I googled and didn't find a reply. The point is, how can I know - at a certain node - that I've just come to it vs I've finished everything underneath it?

like image 794
OmarOthman Avatar asked Apr 29 '12 11:04

OmarOthman


People also ask

Can tree traversal be done without recursion?

You can implement inorder traversal without using recursion using a stack and using Morris Traversal.

How do you traverse a binary tree in postorder traversal without recursion?

a) Push root's right child and then root to stack. b) Set root as root's left child. 2.2 Pop an item from stack and set it as root. a) If the popped item has a right child and the right child is at top of stack, then remove the right child from stack, push the root back and set root as root's right child.

Can we construct BST from inorder traversal?

Yes it is possible to construct a binary search tree from an inorder traversal.

What is postorder traversal without recursion?

PostOrder Traversal without Recursion is a traversal method, where the left subtree is visited first, then right sub tree, and finally root node. Unlike array and linked lists, being linear data structures, we have several ways of traversing binary tree due to its hierarchical nature.

How to traversing binary tree using stack?

Below is an algorithm for traversing binary tree using stack. See this for step wise step execution of the algorithm. 1) Create an empty stack S. 2) Initialize current node as root 3) Push the current node to S and set current = current->left until current is NULL 4) If current is NULL and stack is not empty then a) Pop the top item from stack.

How do you traverse a tree in order without recursion?

Inorder Tree Traversal without Recursion. Using Stack is the obvious way to traverse tree without recursion. Below is an algorithm for traversing binary tree using stack. See this for step wise step execution of the algorithm.

Is it possible to use one stack for post order traversal?

IMHO this algorithm is easier to follow than well performing and readable wikipedia.org / Tree_traversal pseudocode. For glorious details see answers to binary tree exercises in Knuth’s Volume 1. Show activity on this post. Show activity on this post. So you can use one stack to do a post order traversal. Show activity on this post. 1.


1 Answers

You can do that, you just need to remember the last visited node along with the current node. Doing this is not disallowed by the problem statement: both visited flag on each node and a stack are (worst case) O(n), remembering the last node is just O(1).

In C#, the algorithm could look like this:

static void Walk(Node node)
{
    Node lastNode = null;
    while (node != null)
    {
        if (lastNode == node.Parent)
        {
            if (node.Left != null)
            {
                lastNode = node;
                node = node.Left;
                continue;
            }
            else
                lastNode = null;
        }
        if (lastNode == node.Left)
        {
            Output(node);

            if (node.Right != null)
            {
                lastNode = node;
                node = node.Right;
                continue;
            }
            else
                lastNode = null;
        }
        if (lastNode == node.Right)
        {
            lastNode = node;
            node = node.Parent;
        }
    }
}
like image 76
svick Avatar answered Oct 13 '22 18:10

svick