Company logo
  • Empleos
  • Bootcamp
  • Acerca de nosotros
  • Para profesionales
    • Inicio
    • Empleos
    • Cursos y retos
    • Preguntas
    • Profesores
    • Bootcamp
  • Para empresas
    • Inicio
    • Nuestro proceso
    • Planes
    • Pruebas
    • Nómina
    • Blog
    • Calculadora

0

45
Vistas
how do you find the smallest n elements in a binary search tree?

I tried this but it's printing the entire tree:

function inOrder(root, i, n) {
    if (!root) return;
    inOrder(root.left, i, n);
    if(i++ < n) console.log(root.key);
    inOrder(root.right, i, n);
}
6 months ago · Santiago Gelvez
1 Respuestas
Responde la pregunta

0

This happens because i++ only changes the local variable. It doesn't change the i variable of the caller, and so the increments done within the traversal of left subtree will not have any influence on the value of i that is passed to the second recursive call.

You can solve this in many ways, but one is to let each recursive call return the value of their i back to the caller, so the caller can take it to update their own i and continue with that value.

Some other remarks:

  • Once i has reached the value of n, there is no use in still making a recursive call, so exit the function immediately when that happens

  • Instead of letting i increment, let n decrement. That way you only need one extra argument instead of two.

function inOrder(root, n) { // No more `i`
    if (!root) return n;
    n = inOrder(root.left, n);
    if (n-- <= 0) return n; // decrement instead of increment now & exit
    console.log(root.key);
    return inOrder(root.right, n);
}

class Node { // Definition of class to make the demo work
    constructor(key) {
        this.key = key;
        this.left = this.right = null;
    }
    static from(...keys) {
        if (!keys.length) return;
        const root = new Node(keys.shift());
        for (const key of keys) root.add(key);
        return root;
    }
    add(key) {
        if (key < this.key) {
            if (this.left) this.left.add(key);
            else this.left = new Node(key);
        } else {
            if (this.right) this.right.add(key);
            else this.right = new Node(key);
        }
    }
}

// demo
const root = Node.from(5, 13, 4, 7, 11, 1, 8, 12, 9, 3, 2, 6, 10);
inOrder(root, 6);

6 months ago · Santiago Gelvez Denunciar
Responde la pregunta
Encuentra empleos remotos

¡Descubre la nueva forma de encontrar empleo!

Top de empleos
Top categorías de empleo
Empresas
Publicar empleo Planes Nuestro proceso Comercial
Legal
Términos y condiciones Política de privacidad
© 2023 PeakU Inc. All Rights Reserved.