326. Preorder Traversal
Print the values in preorder: the node first, then everything in its left subtree, then everything in its right subtree.
4
/ \
2 6 preorder is 4 2 1 3 6 5 7
/ \ / \
1 3 5 7
Preorder visits a node BEFORE its children, which is what makes it the natural order for copying a tree: the parent exists before anything needs to hang off it.
Writing this with an explicit stack has one detail worth meeting now. A stack reverses what you push, so to pop the left child first you must push the RIGHT child first.
Constraints - `1 ≤ n ≤ 100000` - `-1000000000 ≤ value ≤ 1000000000` - The input always forms a valid tree rooted at node 1.
Input
The first line contains an integer n, the number of nodes.
The second line contains n values, where node i holds the ith value.
Each of the next n lines contains two integers, the left and right child of
node i, using 0 for no child. Node 1 is the root.
Output
Print the values in preorder, separated by single spaces.
Hints
Four rungs, in order. The last two open once you have submitted an attempt. A wrong one counts.