# Binary Tree Traversal

The binary tree node is defined as follows:

## Inorder Traversal

In inorder traversal, the parent node is in between its left and right child nodes. The idea is to first traverse to the leftmost node and then process the node itself, followed by processing its right child node.

## Preorder Traversal

In preorder traversal, the parent node is processed first followed by its left and right child nodes.

$\text{node}\to \text{left}\to \text{right}$We can implement it using a stack. As we iterate through the tree, first process the node itself,
then append its child nodes to the stack. Note that in order to ensure the *left* child node is processed first,
we need to append the *right* child node first.

## Postorder Traversal

Postorder traversal can be implemented in a similar fashion as preorder traversal. Notice that in preorder traversal, we process the node itself followed by its left and right child nodes.

$\text{node}\to \text{left}\to \text{right}$In postorder traversal, we process its left and right child nodes first, followed by the node itself.

$\text{left}\to \text{right}\to \text{node}$Therefore we can reuse the implementation of preorder traversal, and the only difference is that we need to reverse the order when recording values. One way to do so is, instead of appending the node value at the end of the result list, we insert it at the beginning.

Or process the values first and then reverse the result list at the end.