# 🌴 Binary Tree

## How many kinds of binary tree are there?

• Perfect binary tree
• Every node has either 0 or 2 child nodes.
• Complete binary tree
• every level, except possibly the last, is completely filled, and all nodes are as far left as possible.
• Binary search tree
• val(node.left) < val(node.right)
• Balanced binary tree
• The difference of height between left substreet and right subtree differ by no more than 1.

## Different traversal ways

• Pre order: 5, 4, 1, 2, 6, 7, 8
• In order: 1, 4, 2, 5, 7, 6, 8
• Post order: 1, 2, 4, 7, 8, 6, 5

## Traverse in iterative ways

• Pre-order:

• Because we are using a stack, to ensure that we push left node first into the result by popping it out of stack. We have to push right node first.
• In-order

• The result we want is 5, 6, 7
• Post-order
• The order of pre-order is Root, Left, Right, so if we just tweak the order of left, right a bit, then reverse the result, it would be Left, Right, Root!!