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

>Solution :

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