Jimmy Theis

NOV 11, 2013

Programming Interview Question: Level-Order Traversal

I've been subscribed to Brian Jordan's Coding for Interviews weekly emails (which I highly recommend) for a while now, but I've never written up an official solution to any of the weekly questions.

In the meantime, I've become interested in learning more about CoffeeScript (a language that transcompiles to JavaScript), but have never found the time to sit down and really learn about it. So, in an effort to kill two birds with one stone, I'm using CoffeeScript to solve last Friday's interview question:

This week's question is to print a binary tree of integers in level order. Level-order printing means printing each row of the tree from left to right, from root row to the deepest row. After each row, print a newline. For example:

I honestly picked this question because it's one I already know the answer to (and probably so does everyone else who's taken an intro-level data structures class), so I knew I wouldn't spend a bunch of time just figuring out the algorithm.

Anyway, here's my eight-line solution in CoffeeScript:

levelOrder = (rootNode) ->
    queue = [[rootNode, 0]]
    (while queue.length
        [node, level] = queue.pop()
        queue.unshift [node.left, level + 1] if node.left?
        queue.unshift [node.right, level + 1] if node.right?
        node.val + if queue[0]?[1] > level then '\n' else ''
    ).join(' ').replace(/\n\ /g, '\n')

Some of the language features used here include while loops as expressions, conditionals as expressions, destructuring assignment, and the existential operator.

For anyone who's interested, here's the 20 or so lines of JavaScript my code transcompiles to (slightly reformatted):

var levelOrder = function(rootNode) {
    var level, node, queue;
    queue = [[rootNode, 0]];
    return ((function() {
        var _ref, _ref1, _results;
        _results = [];
        while (queue.length) {
            _ref = queue.pop(), node = _ref[0], level = _ref[1];
            if (node.left != null) {
                queue.unshift([node.left, level + 1]);
            }
            if (node.right != null) {
                queue.unshift([node.right, level + 1]);
            }
            _results.push(node.val + (((_ref1 = queue[0]) != null ?
                _ref1[1] : void 0) > level ? '\n' : ''));
        }
        return _results;
    })()).join(' ').replace(/\n\ /g, '\n');
};

I was surprised to see how readable the output code was, which further enforces the idea that CoffeeScript really is just "better" JavaScript (or as the website puts it, "an attempt to expose the good parts of JavaScript in a simple way").

I had a lot of fun using a new language to solve an interview question, and I think I learned a lot about CoffeeScript in the process. I'm not sure if I'll make a habit of this or not; I guess we'll see when the next interview question email comes out.

Cheers!

Google+