[algogeeks] Re: stack using bst
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.
[algogeeks] Re: stack using bst
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.
Re: [algogeeks] Re: stack using bst
@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.
[algogeeks] Re: stack using bst
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.
