# Can a tree be used to create a stack?

I'm aware that linked lists, sets and arrays can be used to create stacks by themselves. The theory behind it is this

`linked-list`: In some languages, a linked-list is substitutable for an array. Stacks are First In First Out operations.

`array`: The `push` and `pop` methods invoke a stack like behavior.

`set`: A set is exactly the same as an array, except it does not feature duplicate elements.

I'm struggling to find a way that a tree can be used to create a stack

• How about a tree that's degenerated to a linked-list? – cmaster Feb 8 '16 at 20:57
• A set is not exactly the same as an array except without duplicates. An array is indexed in order, while a set is explicitly unordered. – Mason Wheeler Feb 8 '16 at 21:05
• A set is not identical to an array without dupes. Iterating over an array is guaranteed to return the objects in the order you put them in the first place. Iterating over a set happens in some other order, defined by the implementation. (for example Python sets are iterated in no particular order, while C++ sets are iterated in ascending order). – James Youngman Feb 8 '16 at 21:48
• @DavidArno: Even in maths, there is no concept of "the first element of a set". That is what is meant with sets being unordered. – Bart van Ingen Schenau Feb 9 '16 at 8:35
• @DavidArno: The integers have an order, but that has nothing to do with their being a set. – Michael Shaw Feb 9 '16 at 9:45

## 2 Answers

Trivially.

Your stack object simply maintains a tree of ints. The Push operation is identical to the insertion of an item in the tree whose key is one greater than the key in the current maximum. That should be the key in the root note, and the new node becomes the new root.

The Pop operation is removal of the node with the greatest key (the root).

This approach should still work with self-balancing trees, though for those it will be slower (since the maximum key is no longer at the root and so accessing it takes O(ln N) rather than O(1)).

The contents of the stack locations would simply be additional content in the tree nodes.

There is a good answer already given, but you could also implement a max-heap then insert an element with a priority equal to the number of elements currently in your heap.