Good day, I need to implement a program to simualate a Push Down Automata. An unbalanced tree would work great for this where each node can have a finite amount of children.

I just don't know what data structure to use - it would be necessary to traverse through the tree from the root to the leaves and vice versa.

Also the nodes should not be sorted upon insertion and each node must have attributes (id, input_symbol, stack_symbol).
Any help would be appreciated,
Thanks