Implementación de Algoritmo DFS en Árboles Binarios con Golang

Clase 13 de 52 • Curso de Algoritmos Avanzados: Grafos y Árboles

Resumen

¿Cómo se implementa un árbol binario en Golang?

Para los desarrolladores interesados en estructuras de datos, especialmente aquellos trabajando con Golang, crear y manejar un árbol binario es un ejercicio invaluable para mejorar las habilidades de codificación. Aquí abordaremos la implementación de un árbol binario en Go.

¿Qué es un nodo en un árbol binario y cómo se describe?

Un nodo en un árbol binario se configura con un valor y, generalmente, dos hijos: uno a la izquierda y otro a la derecha. En el contexto de Golang, puedes definir un nodo de la siguiente manera:

type Nodo struct {
    Valor        int
    NodoIzquierdo *Nodo
    NodoDerecho   *Nodo
}

¿Cuál es la lógica para calcular el total de un árbol?

Al trabajar con un árbol binario, el objetivo puede ser, por ejemplo, calcular la suma de todos los caminos desde la raíz hasta las hojas. Este total iniciará en cero, y si la raíz es nula, simplemente retornamos cero.

var Total int = 0

func calcularTotal(raiz *Nodo) int {
    if raiz == nil {
        return 0
    }
    return Total
}

¿Cómo usar una función DFS para el cálculo de caminos?

Depth-First Search (DFS) es una técnica popular para explorar o recorrer estructuras de datos como grafos y árboles. En este contexto, creamos la función DFS que recibe el nodo actual del árbol, una cadena que representa el camino actual y el total hasta el momento.

func DFS(nodoActual *Nodo, caminoActual string, sumaTotal *int) {
    if nodoActual.NodoIzquierdo == nil && nodoActual.NodoDerecho == nil {
        *sumaTotal += convertirCaminoACadenaYASuma(caminoActual, nodoActual.Valor)
        return
    }

    nuevoCamino := caminoActual + strconv.Itoa(nodoActual.Valor)

    if nodoActual.NodoIzquierdo != nil {
        DFS(nodoActual.NodoIzquierdo, nuevoCamino, sumaTotal)
    }
    if nodoActual.NodoDerecho != nil {
        DFS(nodoActual.NodoDerecho, nuevoCamino, sumaTotal)
    }
}

func convertirCaminoACadenaYASuma(camino string, valor int) int {
    caminoCompleto := camino + strconv.Itoa(valor)
    suma, _ := strconv.Atoi(caminoCompleto)
    return suma
}

¿Por qué es importante realizar pruebas?

Es vital realizar pruebas, sobre todo si estás en un proceso de entrevista donde la precisión y la robustez del código son evaluadas. Las pruebas nos aseguran que la lógica y la solución planteada son correctas.

La importancia de las pruebas incluye:

Validar la lógica: Asegurar que todos los caminos del árbol se calculan correctamente.
Detectar errores: Permite identificar fallas antes de la ejecución de la lógica en situaciones reales.

¿Cómo se pueden realizar pruebas de escritorio o unitarias?

Antes de ejecutar pruebas unitarias automáticas, es clave realizar pruebas de escritorio. Esto implica verificar el resultado esperado paso a paso manualmente. Además, define funciones de prueba en tu código que verifiquen los resultados contra casos de prueba conocidos.

Invito a los lectores a involucrarse practicando crear varias estructuras de árbol y explorando diferentes algoritmos. Comenten su experiencia o compartan cualquier error que hayan encontrado y cómo lo corrigieron. ¡La programación es una habilidad en constante perfeccionamiento!

JOSE EMMANUEL RAMIREZ GUERRERO

student•

Esta es mi solución en Kotlin:

data class Node(
    val value: Int,
    val children: List<Node>? = null,
)

fun main() {
    val root = Node(
        value = 1,
        children = listOf(
            Node(
                value = 3,
                children = listOf(
                    Node(value = 5),
                    Node(value = 8),
                )
            ),
            Node(
                value = 7,
                children = listOf(
                    Node(1)
                )
            )
        )
    )
    val total = dfs(root, "")
    println("The sum is: $total")
}

fun dfs(node: Node, number: String): Int {
    if (node.children == null) {
        return "$number${node.value}".toInt()
    }
    var total = 0
    node.children.forEach {
        total += dfs(it, "$number${node.value}")
    }

    return total
}

JOHANBERT MOSQUERA

student•

No hay solucion que alguien hiciera en JS Javascript? :( jaja en cuanto pueda la hago y la subo jeje

Miguel Angel Reyes Moreno

student•

Tarde pero seguro:

// Definition for a binary tree node.

class TreeNode {

constructor(val = 0, left = null, right = null) {

this.val = val;

this.left = left;

this.right = right;

}

class Solution {

sumNumbers(root) {

const dfs = (node, currentNumber) => {

if (!node) {

return 0;

}

currentNumber = currentNumber * 10 + node.val;

if (!node.left && !node.right) {

return currentNumber;

}

return dfs(node.left, currentNumber) + dfs(node.right, currentNumber);

};

return dfs(root, 0);

}

// Example usage:

const root1 = new TreeNode(1);

root1.left = new TreeNode(2);

root1.right = new TreeNode(3);

const solution = new Solution();

const result = solution.sumNumbers(root1);

console.log(result: ${result});

Andres Silva Vega

student•

Usuario anónimo

user•

Solución en java

class Solution {
    static int total;
    public int sumNumbers(TreeNode root) {
        total = 0;
        dfs(root, 0);
        return total;
    }
    static void dfs(TreeNode root, int parent) {
        int value = (parent * 10) + root.val;
        if(root.left == null && root.right == null){
            total += value;
            return;
        }

        if(root.left != null) {
            dfs(root.left, value);
        }

        if(root.left != null) {
            dfs(root.right, value);
        }
        
        return;

    }
}

Tomás Santa Cruz

student•

Solución en c++

#include <iostream>
#include <vector>

using namespace std;

struct Node
{
    int value;
    vector<Node> childrens;
};

int dfs(const Node &root, int path, int &sum)
{
    if (root.childrens.size() == 0)
    {
        sum += path;
        return sum;
    }

    for (int i = 0; i < root.childrens.size(); i++)
    {
        dfs(root.childrens[i], path * 10 + root.childrens[i].value, sum);
    }
    return sum;
}

int main()
{
    // root
    Node root;
    root.value = 1;

    // child1
    Node child1;
    child1.value = 2;

    // grandchild1
    Node grandchild1;
    grandchild1.value = 4;
    // grandchild2
    Node grandchild2;
    grandchild2.value = 1;

    child1.childrens.push_back(grandchild1);
    child1.childrens.push_back(grandchild2);

    // child2
    Node child2;
    child2.value = 3;
    root.childrens.push_back(child2);

    root.childrens.push_back(child1);
    int result = 0;
    dfs(root, root.value, result);

    cout << result << endl;

    return 0;
}

Leandro Ayala

student•

Puede ser que el error en el codigo es que la variable caminoActual nunca se regenera?

Nicolas Lopez

student•

Mi solucion en Java:public static int treePathSum(NodeTree root, int sum){ if (root == null){return 0;}

// Update the value. sum * 10 to move forward the digit at 1, then + the root.val. sum = sum * 10 + root.val;

// If there isn't more node (leaf node), then return the sum. if(root.left == null && root.right == null){ //System.out.println("root.value -> " + root.val + " sum -> " + sum); return sum; }

// Recursion instead of uses a Stack for iteration. return treePathSum(root.left, sum) + treePathSum(root.right, sum); }

public static int treePathSum(NodeTree root, int sum){
        if (root == null){return 0;}

        // Update the value. sum * 10 to move forward the digit at 1, then + the root.val.
        sum = sum * 10 + root.val;

        // If there isn't more node (leaf node), then return the sum.
        if(root.left == null && root.right == null){
            //System.out.println("root.value -> " + root.val + " sum -> " + sum);
            return sum;
        }

        // Recursion instead of uses a Stack for iteration.
        return treePathSum(root.left, sum) + treePathSum(root.right, sum);
    }

Kellbis Salazar

student•

Que sentido tiene hacer ese codigo y no testear a ver si funciona?

Platzi

student•

Lo que busca la instrucción es enseñar cómo implementar una solución al problema de generar combinaciones a partir de un número de teléfono, usando programación recursiva y brindar la oportunidad de reflexionar sobre la complejidad del algoritmo.

John Eduard Meneses González

student•

My solution!!

Michael Martinez

company_admin•

Siendo sincero la explicación es muy confusa o no cuenta con cualidades para enseñar.

Carlos Guzman

student•

Mi solucion recursiva y enearia con python.

def dfs(root, current_number=''):
    if not root.get('children', False):
        print(current_number)
        return [current_number]

    results = []
    for child in root.get('children', []):
        new_number = f'{current_number}{child.get('value')}'
        result = dfs(child, new_number)
        results.extend(result)

    return results

def sum_root_leaf_number(root):
    numbers_result = dfs(root, str(root.get('value')));

    result = 0
    for number in numbers_result:
        result += int(number)
    return result
```Data de ejemplo:
```js
graph_short = {
    'value': 1,
    'children': [
        {
            'value': 2,
            'children': [
                {'value': 3}
            ]
        },
        {
            'value': 2,
            'children': [
                {'value': 3}
            ]
        }
    ]
}

REYNALDO FABIAN NORIEGA ZAMBRANO

student•

Mi implementacion en C++:

#include<iostream>

using namespace std;


class Node{
	public:
		int val;
		Node *leftNode;
		Node *rightNode;
		Node(int val, Node *leftNode, Node *rightNode){
			this->val = val;
			this->leftNode = leftNode;
			this->rightNode = rightNode;
		}
};


void addValues(Node *root, int &total, int current){
	if(!root) return;

	current = 10*current + root->val;
	if(!root->leftNode && !root->rightNode){
		total += current;
	}
	if(root->leftNode){
		addValues(root->leftNode, total, current);
	}
	if(root->rightNode){
		addValues(root->rightNode, total, current);
	}

}



int main(){

	int total = 0;
	int current = 0;

	Node *node5 = new Node(5, NULL, NULL);
	Node *node8 = new Node(8, NULL, NULL);
	Node *node7 = new Node(7, NULL, NULL);
	Node *node3 = new Node(3, node5, node8);
	Node *node2 = new Node(2, node7, NULL);
	Node *bT = new Node(1, node3, node2);

	addValues(bT, total, current);

	cout <<  "total = " << total << endl;
	return 0;
}

Cristian Toro

student•

Solución en Python

def Sum_Root(nodo):
    if not nodo:
        return 0
    
    return dfs(nodo)

def dfs(nodo , caminoActual=""):
    if not nodo.izquierda and not nodo.derecha:
        return int(caminoActual + str(nodo.valor))
    
    total = 0

    if nodo.izquierda:
        total += dfs(nodo.izquierda , caminoActual + str(nodo.valor))

    if nodo.derecha:
        total += dfs(nodo.derecha , caminoActual + str(nodo.valor))

    return total

Miguel Angel Reyes Moreno

student•

Código un poco más simplificado:

package main import ( "fmt") // TreeNode represents a node in a binary tree.type TreeNode struct { Val int Left *TreeNode Right *TreeNode} // sumNumbers function calculates the sum of all numbers formed by root-to-leaf paths.func sumNumbers(root *TreeNode) int { var dfs func(node *TreeNode, currentNumber int) int dfs = func(node *TreeNode, currentNumber int) int { if node == nil { return 0 } currentNumber = currentNumber*10 + node.Val if node.Left == nil && node.Right == nil { return currentNumber } return dfs(node.Left, currentNumber) + dfs(node.Right, currentNumber) } return dfs(root, 0)} func main() { // Example usage: root := &TreeNode{Val: 1} root.Left = &TreeNode{Val: 2} root.Right = &TreeNode{Val: 3} result := sumNumbers(root) fmt.Printf("result: %d\n", result)}

Hans Arias

student•

Esta es mi solucion en Node.js

var total = 0;

const sumNumbers = (root) => {
    if (nodeIsEmpty(root)) return 0;

    let sumTxt = String(root.content);
    dfs(root, sumTxt);

    console.log("Total ", total);
}

const dfs = (node, sumTxt) => {
    if (nodeIsEmpty(node.right) && nodeIsEmpty(node.left)) {
        total = total + Number(sumTxt);
    };

    calculateSum(node.right, sumTxt, total);
    calculateSum(node.left, sumTxt, total);
}

const nodeIsEmpty = (node) => {
    return node == undefined || Object.keys(node).length == 0;
}

const calculateSum = (node, sumTxt) => {
    if (nodeIsEmpty(node)) return;

    dfs(node, sumTxt + String(node.content));
}

const root = {
    content: 1,
    visited: false,
    right : {
        content: 3,
        visited: false,
        right : {
            content: 5,
            visited: false,
            right: {},
            left: {}
        },
        left: {
            content: 8,
            visited: false,
            right: {},
            left: {}
        }
    },
    left: {
        content: 7,
        visited: false,
        right: {},
        left: {
            content: 1,
            visited: false,
            right: {},
            left: {}
        }
    }
}

sumNumbers(root);

Alexander Palazuelos

student•

Aquí está mi solución, un poco rudimentaria pero sirve.

totalF = 0

class Node:
    def __init__(self, valor):
        self.valor = valor
        self.izquierda = None
        self.derecha = None

nodo1 = Node(1)
nodo2 = Node(2)
nodo3 = Node(3)
nodo4 = Node(4)
nodo5 = Node(5)
nodo6 = Node(6)

nodo1.izquierda = nodo2
nodo1.derecha = nodo3
nodo2.izquierda = nodo4
nodo2.derecha = nodo5
nodo3.izquierda = nodo6

def sum_numbers(nodo):
    if nodo == None:
        return 0
    dfs(nodo, "", 0)
    return totalF

def dfs(nodoAct, cadenaSuma, total):
    global totalF
    if(nodoAct.izquierda == None and nodoAct.derecha == None):
        total += int((cadenaSuma) + str(nodoAct.valor))
    if(nodoAct.izquierda != None):
        dfs(nodoAct.izquierda, cadenaSuma+str(nodoAct.valor), total)
    if(nodoAct.derecha != None):
        dfs(nodoAct.derecha, cadenaSuma+str(nodoAct.valor), total)
    if totalF != total:
     totalF += total
    else: return totalF

print(sum_numbers(nodo1))


    
```totalF = 0
*class* <u>Node</u>:    *def* \_\_init\_\_(*self*, *valor*):        *self*.valor = *valor*        *self*.izquierda = None        *self*.derecha = None
nodo1 = <u>Node</u>(1)nodo2 = <u>Node</u>(2)nodo3 = <u>Node</u>(3)nodo4 = <u>Node</u>(4)nodo5 = <u>Node</u>(5)nodo6 = <u>Node</u>(6)
nodo1.izquierda = nodo2nodo1.derecha = nodo3nodo2.izquierda = nodo4nodo2.derecha = nodo5nodo3.izquierda = nodo6
*def* sum\_numbers(*nodo*):    if *nodo* == None:        return 0    dfs(*nodo*, "", 0)    return totalF
*def* dfs(*nodoAct*, *cadenaSuma*, *total*):    global totalF    if(*nodoAct*.izquierda == None and *nodoAct*.derecha == None):        *total* += <u>int</u>(*(cadenaSuma)* + <u>str</u>(*nodoAct*.valor))    if(*nodoAct*.izquierda != None):        dfs(*nodoAct*.izquierda, *cadenaSuma*+<u>str</u>(*nodoAct*.valor), *total*)    if(*nodoAct*.derecha != None):        dfs(*nodoAct*.derecha, *cadenaSuma*+<u>str</u>(*nodoAct*.valor), *total*)    if totalF != *total*:     totalF += *total*    else: return totalF
print(sum\_numbers(nodo1))

   &#x20;

Daniel Ortiz

student•

Despues de pensar un poco lo logre


class Response:
    total = 0

    def __init__(self, total):
        self.total = total

    def dfs(self, node, valor_actual):
        parcial = valor_actual + str(node.valor)

        if node.izquierda is None and node.derecha is None:
            self.total = self.total + int(parcial)
        if node.derecha is not None:
            self.dfs(node.derecha, parcial)
        if node.izquierda is not None:
           self.dfs(node.izquierda, parcial)


def sum_numbers(node, valor_actual=''):
    response = Response(0)
    response.dfs(node, valor_actual)
    return response.total

Harold Zurita Simon

student•

Hola 😄, les comparto la solución en Golang junto a la prueba. . solSRLN.go:

package main

import (
	"fmt"
	"strconv"
)

// Definición de la estructura del árbol
type Nodo struct {
	Val       int
	izquierda *Nodo
	derecha   *Nodo
}

// Creación del árbol
var arbolSRLN = &Nodo{
	Val: 1,
	izquierda: &Nodo{
		Val: 3,
		izquierda: &Nodo{
			Val:       5,
			izquierda: nil,
			derecha:   nil,
		},
		derecha: &Nodo{
			Val:       8,
			izquierda: nil,
			derecha:   nil,
		},
	},
	derecha: &Nodo{
		Val:       7,
		izquierda: nil,
		derecha: &Nodo{
			Val:       1,
			izquierda: nil,
			derecha:   nil,
		},
	},
}

// Función que realiza la suma de los números del árbol
func sumNumbers(raiz *Nodo) int {
	if raiz == nil {
		return 0
	}
	total := 0
	dfs(raiz, "", &total)
	return total
}

// Función DFS recursiva para recorrer el árbol y sumar los números
func dfs(raiz *Nodo, caminoActual string, sumaTotal *int) {
	if raiz.izquierda == nil && raiz.derecha == nil {
		valor, _ := strconv.Atoi(caminoActual + strconv.Itoa(raiz.Val))
		*sumaTotal += valor
	}
	if raiz.izquierda != nil {
		dfs(raiz.izquierda, caminoActual+strconv.Itoa(raiz.Val), sumaTotal)
	}
	if raiz.derecha != nil {
		dfs(raiz.derecha, caminoActual+strconv.Itoa(raiz.Val), sumaTotal)
	}
}

func main() {
	fmt.Println(sumNumbers(arbolSRLN))
}

. Output:

German Lozickyj

student•

Mi solucion en Python :

def sum_root_regresive(root):
    left = sum_function(root, 'left')
    right = sum_function(root, 'right')
    return left + right

def sum_function(root, direction, str_queue = ''):
    if root.get(direction) == None:
        return int(str_queue + str(root['value']))
    
    return sum_function(root[direction], direction, str_queue + str(root['value']))

Luis Angel Armenta Delgadillo

student•

Mi solución recursiva en python:

def sum_numbers(root: Node, start_number_with: str = '') -> int:
  if root.left is None and root.right is None:
    return int(start_number_with + str(root.value))
  
  left = 0
  right = 0
  
  if root.left is not None:
    left = sum_numbers(root.left, start_number_with + str(root.value))
  if root.right is not None:
    right = sum_numbers(root.right, start_number_with + str(root.value))

  
  return left + right