Recursive Solutions - O(1) Space Complexity

With Tail Call Optimization, recursive solutions can be implemented with O(1) space complexity.

I was solving LeetCode #1008 in the "Stack" section, and the recursive solution stood out to me first. As this is part of the "Stack" category, and I've been focusing on learning the stack data structure better, I wrote both solutions.

I always liked the recursive solutions for their simplicity and ease of understanding. I've heard they're not favored as there is a call stack depth that can be a problem for large inputs and poorly written code. However, an old talk from Douglas Crockford popped into my mind where he talks about JavaScript getting proper tail-call recursion (or Tail Call Optimization). I was curious, so I looked into it and found most engines support it since 2022. This means, essentially, that the call stack is not filled up with recursive calls, and the space complexity is O(1) for recursive solutions. This makes the recursive solution clearly superior in my mind. Not only is more easily understood, it's also more space efficient. Both solution here are O(n) time complexity.

Recursive Solution

function bstFromPreorder(preorder: number[]): TreeNode | null {
    const [first, ...rest] = preorder;
    const [left, right] = [[], []];
 
    rest.forEach((value) => {
        if (first > value) {
            left.push(value);
        } else {
            right.push(value);
        }
    });
 
    return new TreeNode(
        first,
        left.length < 1 ? null : bstFromPreorder(left),
        right.length < 1 ? null : bstFromPreorder(right),
    );
};

Iterative Solution

I've implemented a custom stack to make the code clearer for my own understanding

function createStack() {
    const stack = Object.create([]);
 
    stack.top = function () {
        return stack[stack.length - 1];
    };
 
    stack.topValue = function () {
        const topNode = stack.top();
        return topNode ? topNode.val : NaN;
    };
 
    return stack;
}
 
function bstFromPreorder(preorder) {
    const [first, ...rest] = preorder;
    const root = new TreeNode(first);
    const stack = createStack();
 
    stack.push(root);
 
    rest.forEach((value) => {
        let parent = null;
 
        while (stack.length > 0 && stack.topValue() < value) {
            parent = stack.pop();
        }
 
        if (parent) {
            parent.right = new TreeNode(value);
            stack.push(parent.right);
        } else {
            parent = stack.top();
            parent.left = new TreeNode(value);
            stack.push(parent.left);
        }
    });
 
    return root;
}