So, in short you are using a BST and a FIFO linked list. Whereas, a
Stack is actually a LIFO linked list. Am i right?
On Aug 25, 11:37 pm, Don <dondod...@gmail.com> wrote:
> 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.
