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