Apuntes_Python/03_arbol_binario/README.md

# Binary Tree

## ¿Que es un Arbol? (Tree)

Un árbol contiene **nodos**, generalmente represantados como círculos  
Un nodo contener otros nodos, el punto que une un nodo con otro  
es llamado **edge** (borde)

```mermaid
graph TD
    id1((A)) --> id2((B))
    id2((B)) --> id3((D))
    id2((B)) --> id4((E))
    id1((A)) --> id5((C))
    id5((C)) --> id6((F))
```
Estos nodos pueden representar cualquier objeto.  
Los nodos tienen relaciones unos con otros:
  - **B** es padre de **D** y **E** (parent) 
  - **D** y **E** son hijos de **B** (child)
  - **A** es el nodo raíz (root), no tiene padres  
  - **D**, **E** y **F** son nodos hoja (leaf), no tienen hijos  

En el gráfico superior, los nodos **leaf** están a 2 niveles del nodo **root**
  
En el sgte. grafico los nodos **leaf** (**C**, **D** y **E**) están en distinto nivel  
```mermaid
graph TD
    id1((A)) --> id2((B))
    id2((B)) --> id3((D))
    id2((B)) --> id4((E))
    id1((A)) --> id5((C))
```

## Binary Tree

Binario tiene relacion al número 2. Un árbol binario es un árbol cuyos nodos tienen:  
  - máximo **2 hijos**  
  - solo **una raíz** (root)
  - solo **una ruta** entre entre nodos   
  
  
### No son arboles binarios:  

  * **A** tiene 3 nodos hijos
```mermaid
graph TD
    id1((A)) --> id2((B))
    id2((B)) --> id3((D))
    id2((B)) --> id4((E))
    id1((A)) --> id5((C))
    id1((A)) --> id6((F))
```
<br>
<br>

  * **C** tiene dos nodos raíz
```mermaid
graph TD
    id1((A)) --> id2((B))
    id2((B)) --> id3((D))
    id2((B)) --> id4((E))
    id1((A)) --> id5((C))
    id5((C)) --> id6((F))
    id7((G)) --> id5((C))
```
<br>
<br>

  * El nodo **'E'** tiene dos rutas posibles (A, B, E) y (A, C, F)
```mermaid
graph TD
    id1((A)) --> id2((B))
    id2((B)) --> id3((D))
    id2((B)) --> id4((E))
    id1((A)) --> id5((C))
    id5((C)) --> id6((F))
    id5((C)) --> id4((E))
```
<br>
<br>

  * Ningún nodo es root y hay infinitas rutas a los nodos
```mermaid
graph TD
    id1((A)) --> id2((B))
    id2((B)) --> id3((C))
    id3((C)) --> id1((A))
```
<br>
<br>

### Son considerados árbol binario:
  
  * Arbol con 1 root y 2 nodos child
```mermaid
graph TD
    id1((A)) --> id2((B))
    id1((A)) --> id5((C))
```
<br>
<br>

  * Arbol con 1 root y 1 nodo child
```mermaid
graph TD
    id1((  A  )) --> id2((  B  ))
```
<br>
<br>

  * Arbol único
```mermaid
graph TD
    id1((  A  ))
```
<br>
<br>

  * Arbol vacío (empty tree)
  
<br>
<br>
  
## Clase Arbol Binario

Representación de árbol binario con algún lenguaje de programación
  - Cada nodo es un objeto (una instancia de clase)
  - Las propiedades de un nodo son:
    * Su valor
    * Su referencia a nodos hijos (nodo.left, nodo.right)

```python
class Nodo:
    def __init__(self, val, left=None, right=None):
        self.val = val
        self.left = left
        self.right = right
```
<br>

----

## Funciones para Arboles Binarios
### Retornar valores
Prioridad valores de nodo hijo sobre valores de nodo del mismo nivel
```python
def ValoresLejanosPrioridad(self):
    """
    retorna valor de nodos priorizando profundidad a nivel (de izquierda a derecha)
    usando recursividad y desempaquetado de lista (operador '*')
    """
    if self is None:
        return []
    val_izq = ValoresLejanosPrioridad(self.left)
    val_der = ValoresLejanosPrioridad(self.right)
    return [self.val, *val_izq, *val_der]
```
<br>

Prioridad valores de nodos mismo nivel
```python
from collections import deque

def ValoresPrioridadNivel(self):
    """
    retorna valor de nodos de un arbol binario priorizando nodos
    del mismo nivel (de izquierda a derecha), usando una lista
    como cola (fifo)
    """
    cola = deque([self])
    valores = []
    if self == None:
        return []
    while cola:
        actual = cola.popleft()
        valores.append(actual.val)
        if actual.left:
            cola.append(actual.left)
        if actual.right:
            cola.append(actual.right)
    return valores
```
<br>

### Comprobar un valor

```python
def ArbolIncluye(self, valor):    
    """    
    retorna booleano según existencia en árbol binario    
    del valor consultado, utilizando recursión    
    """    
    if self is None:    
        return False    
    if self.val == valor:    
        return True    
    return ArbolIncluye(self.left, valor) or ArbolIncluye(self.right, valor)    
```
<br>

### Suma de Valores
```python
def SumaValores(self):
    """
    retorna la suma de todos los valores del árbol binario
    recursivamente.
    """
    if self is None:
        return 0
    return self.val + SumaValores(self.left) + SumaValores(self.right)
```
<br>

### Valor Mínimo
```python
def ValorMinimo(self):
    """
    retorna el valor mínimo en árbol binario usando recursividad
    """
    if self is None:
        return inf
    min_izq = ValorMinimo(self.left)
    min_der = ValorMinimo(self.right)
    return min(self.val, min_izq, min_der)
```
<br>

### Ruta con mayor suma
```python
def SumaMayorDeRutas(self):
    """
    retorna la suma de los valores de la ruta(root-leaf) del 
    árbol binario, cuya suma sea mayor. Usando recursión
    """
    if self is None:
        return -inf
    if self.left is None and self.right is None:
        return self.val
    mayor = max(SumaMayorDeRutas(self.left), SumaMayorDeRutas(self.right))
    return self.val + mayor
```
<br>

----

## TestRunner

[github.com/viniciusd](https://gist.github.com/viniciusd/73e6eccd39dea5e714b1464e3c47e067)