---
# System prepended metadata

title: Binary Tree
tags: [tree, data structure]

---

![](https://hackmd.io/_uploads/BJO6W1Eth.png)

Binary Tree condition(only):child 不能超過2個

![](https://hackmd.io/_uploads/S1jPf1NYn.png)


# Complite Binary Tree 

Every leve 必須被填滿

除了最後一層 但node 必須靠左

![](https://hackmd.io/_uploads/S1CqmJVK2.png)


# Perface Binary Tree 

All level well be complete filled !!


![](https://hackmd.io/_uploads/rk467JEK2.png)

![](https://hackmd.io/_uploads/ryLHEJEtn.png)

![](https://hackmd.io/_uploads/B1PlH1EFn.png)


# Balanced Binary Tree 

減少operation cost time 

left tree 跟 right tree 的 difference 不能超過 1 

![](https://hackmd.io/_uploads/Bkbnd14t2.png)


Difference 計算 = |Hight(Left sub Tree) - Hight(Right Sub Tree)|

![](https://hackmd.io/_uploads/rJGcd1VYn.png)


Non-blanced 
![](https://hackmd.io/_uploads/BkXRwyEFh.png)

    
Node2 -> |1 - (-1)| = 2 (不平衡)

# Store Binary Tree in memory 

## Dynamically create nodes (Pointer/Reference)

creat linked node to each other useing the pointer

![](https://hackmd.io/_uploads/BJTKYJVF2.png)


## Array (used for heap)

![](https://hackmd.io/_uploads/S12Uq1NYn.png)

![](https://hackmd.io/_uploads/SkwDcJEY2.png)
### complite tree 
```
for node at index i 
    Left node index = 2i + 1
    Right node index = 2i + 2
```