You will have to keep two pointers, one to the root of the tree and
one to the head of the FIFO linked list.
To push, insert the item into both the bst and the linked list.
To pop, set a pointer to the first item in the linked list. Delete it
from the bst. It will always be a leaf, so deleting should be easy.
Follow the parent pointer up one level and set the appropriate left or
right pointer to null. Then set the head of the linked list to the
next item in the list. Return the pointer to the former first item.
push(node n)
{
tree.insert(n); // O(log n)
n->next = stack;
stack = n;
}
node pop()
{
node result = stack;
if (result->parent->left == result) result->parent->left = 0;
else result->parent->right = 0;
stack = result->next;
result->next = 0;
return result;
}
I was mistaken when I said push was O(1). Later on I said O(log n)
which is correct.
Don
On Aug 25, 1:25 pm, shady <sinv...@gmail.com> wrote:
> @don how will you keep track of the latest element inserted in a bst.... ?
> O(1) for pop ? similarly how to get O(1) for push ?
>
> Stack can be implemented with bst but the time complexity will increase.
>
> Anyone with different views ?
>
> On Thu, Aug 25, 2011 at 11:37 PM, Don <dondod...@gmail.com> wrote:
> > The only way I see to be able to search in O(log n) and push/pop in
> > O(1) would be to have each node contain 4 pointers: left, right, and
> > parent pointers for the binary search tree and next pointer for the
> > stack linked list. The stack would be a linked list using the "next"
> > pointer, and the search tree would allow quick searching. Insertion
> > and searching would be O(log n) as with any binary search tree. Pop
> > would be O(1).
>
> > If you don't need to be able to search, just use the "left" pointer to
> > make a linked list. Push and pop are both O(1), but you don't have a
> > binary search tree any more.
>
> > Don
>
> > On Aug 25, 12:00 pm, prasanth n <nprasnt...@gmail.com> wrote:
> > > how to implement a stack(push and pop) using binary search tree??
>
> > > --
> > > *prasanth*
>
> > --
> > You received this message because you are subscribed to the Google Groups
> > "Algorithm Geeks" group.
> > To post to this group, send email to algogeeks@googlegroups.com.
> > To unsubscribe from this group, send email to
> > algogeeks+unsubscr...@googlegroups.com.
> > 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 algogeeks@googlegroups.com.
To unsubscribe from this group, send email to
algogeeks+unsubscr...@googlegroups.com.
For more options, visit this group at
http://groups.google.com/group/algogeeks?hl=en.
