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 <[email protected]> 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 [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.
