Menu
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?
794
You can implement inorder traversal without using recursion using a stack and using Morris Traversal.
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.
Yes it is possible to construct a binary search tree from an inorder traversal.
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.
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.
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.
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.
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;
}
}
}
If you love us? You can donate to us via Paypal or buy me a coffee so we can maintain and grow! Thank you!
Donate Us With
