327. Inorder Traversal
Print the values in inorder: everything in the left subtree, then the node, then everything in the right subtree.
4
/ \
2 6 inorder is 1 2 3 4 5 6 7
/ \ / \
1 3 5 7
That example is not a coincidence. The tree is a binary search tree, and the inorder traversal of a BST comes out sorted. That single fact is why inorder is the traversal worth knowing best, and problem 331 relies on it.
The iterative version is harder than preorder, because a node must be visited AFTER its left subtree, so it has to be remembered while that subtree is walked.
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 inorder, separated by single spaces.
Hints
Four rungs, in order. The last two open once you have submitted an attempt. A wrong one counts.