It turns out preorder is enough if you know it was generated from a
BST. Inorder is needed if it was an arbitrary tree.
One way to code the algorithm is with a stack to hold nodes that
already have a left child and might still need a right one.
// assume: unique keys
// root is the tree we're building
// current is the last node read; invariant is it has no children yet
// stack S holds nodes with a left child that still might need a
right.
// Invariant: top(S) is smallest key in stack
// and all stacked keys are less than current.
S = empty
root = current = new node created from input
while not end of input {
p = new node created from input
if (p->key < current->key) {
// new node becomes left child of current
current->left = p;
// and is now waiting a right child
push(S, current);
}
else {
// new node is a right child; find its parent:
// the largest of the set union({current}, S)
// that is less than current.
parent = current;
while (top(S)->key < p->key)
parent = pop(S);
// popping has restored stack invariant
parent->right = p;
}
// restore invariant on current
current = p;
}
On Oct 18, 2:09 am, payal gupta <[email protected]> wrote:
> hey,i guess a specific binary tree is not possible...by d use of jst a
> preorder...
> 4 a specific tree inorder is also reqd...
> dere will be many trees posible...sso is it dat v got 2 make all possible
> tree vth d given preorder???
>
>
>
>
>
>
>
> On Tue, Oct 18, 2011 at 10:12 AM, Ankuj Gupta <[email protected]> wrote:
> > How to reconstruct a BST from just the prorder traversal of that tree ?
>
> > --
> > You received this message because you are subscribed to the Google Groups
> > "Algorithm Geeks" group.
> > To post to this group, send email to [email protected].
> > To unsubscribe from this group, send email to
> > [email protected].
> > For more options, visit this group at
> >http://groups.google.com/group/algogeeks?hl=en.
--
You received this message because you are subscribed to the Google Groups
"Algorithm Geeks" group.
To post to this group, send email to [email protected].
To unsubscribe from this group, send email to
[email protected].
For more options, visit this group at
http://groups.google.com/group/algogeeks?hl=en.
