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);
}
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);