Non-Linear Structures

Binary Search Trees (BST)

Nodes, pointers, references, and in-order traversal in C, Java, JS, and Python.

1. BST Fundamental Property

In a BST, for any node X: left subtree values are smaller (< X) and right subtree values are larger (> X). In-order traversal yields sorted elements.

NODE STRUCTURE

Valor / KeyDato del nodo

Puntero / Ref IzquierdaSubárbol < Key

Puntero / Ref DerechaSubárbol > Key

2. C: struct Node con Punteros

En C se define con `struct Node` y punteros auto-referenciados `struct Node *left, *right`.

bst.c

typedef struct Node {
    int data;
    struct Node *left;
    struct Node *right;
} Node;

Node* createNode(int val) {
    Node* n = (Node*)malloc(sizeof(Node));
    n->data = val; n->left = n->right = NULL;
    return n;
}

3. Java: Clase TreeNode

Java maneja las conexiones del árbol mediante referencias a objetos en el Heap.

BST.java

class TreeNode {
    int val;
    TreeNode left, right;
    TreeNode(int val) { this.val = val; }
}

4. JavaScript: Clases ES6

JS implementa la estructura con clases de ES6 y punteros `null` para hojas.

bst.js

class Node {
    constructor(value) {
        this.value = value;
        this.left = null;
        this.right = null;
    }
}

5. Python: Recorrido In-Order Recursivo

El recorrido In-Order (Izquierda ➔ Raíz ➔ Derecha) visita los nodos de menor a mayor valor.

bst.py

class Node:
    def __init__(self, val):
        self.val = val
        self.left = None
        self.right = None

def in_order(root):
    if root:
        in_order(root.left)
        print(root.val)
        in_order(root.right)

6. BST Inspector

Árbol con Raíz 10, Izq 5, Der 15

Recorrido In-Order ➔ 5, 10, 15 (Secuencia Ordenada)