Intenté esto pero está imprimiendo todo el árbol:
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); }
Esto sucede porque i++
solo cambia la variable local . No cambia la variable i
de la persona que llama, por lo que los incrementos realizados dentro del recorrido del subárbol izquierdo no tendrán ninguna influencia en el valor de i
que se pasa a la segunda llamada recursiva.
Puede resolver esto de muchas maneras, pero una es permitir que cada llamada recursiva devuelva el valor de su i
a la persona que llama, de modo que la persona que llama pueda tomarlo para actualizar su propia i
y continuar con ese valor.
Algunas otras observaciones:
Una vez que i
alcanzado el valor de n
, no sirve de nada seguir haciendo una llamada recursiva, así que salga de la función inmediatamente cuando eso suceda.
En lugar de dejar que i
incremente, deje que n
disminuya . De esa manera, solo necesita un argumento adicional en lugar de dos .
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);