# ðŸŒ´ Binary Tree

## How many kinds of binary tree are there?

- Perfect binary tree
- Every node has either
`0`

or`2`

child nodes.

- Every node has either
- Complete binary tree
- every level, except possibly the last, is completely
`filled`

, and all nodes are as`far left`

as possible.

- every level, except possibly the last, is completely
- 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`

.

- The difference of height between

## 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

## How to define your own tree node?

1 | unction TreeNode(val, left, right) { |

## 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.1

2

3

4

5

6

7

8

9

10

11var preorderTraversal = function(root, result = []) {

if (!root) return result;

let stack = [root];

while (stack.length > 0) {

let cur = stack.pop();

result.push(cur.val);

cur.right && stack.push(cur.right);

cur.left && stack.push(cur.left);

}

return result;

}

- Because we are using a
`In-order`

- Think about this particular tree.
- The result we want is
`5, 6, 7`

1 | function inorderTraversal(root, result = []) { |

`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`

!!

- The order of

1 | var postorderTraversal = function(root, result = []) { |