Tree traversal order

(Referring to this leetcode problem)

My first solution was, of course, recursive:

class Solution {
public:
    vector<int> postorderTraversal(TreeNode* root) {
        vector<int> ans;
        traverse(ans, root);
        return ans;
    }

    void traverse(vector<int>& ans, TreeNode* node) {
        if (!node) return;          // *
        traverse(ans, node->left);  // *
        traverse(ans, node->right); // *
        ans.push_back(node->val);   // *
    }
};

However, the problem suggests that the reader try an iterative solution instead.

While doing that, I tried to keep the essential parts (marked with *) of the algorithm identical, while only modeling the recursion with a stack:

// Pattern: discriminated union
struct Action {
    enum Tag { TRAVERSE, SHOW };
    
    Tag tag;
    union {
        TreeNode *node;
        int value;
    };
    
    Action(TreeNode *node)
        : tag{TRAVERSE}, node{node}
    {}
    
    Action(int value)
        : tag{SHOW}, value{value}
    {}
};

class Solution {
public:
    vector<int> postorderTraversal(TreeNode* root) {
        vector<int> ans;
        
        stack<Action> actions;
        actions.push(Action{root});
        
        while (!actions.empty()) {
            auto action = actions.top();
            actions.pop();

            stack<Action> tmp;

            switch (action.tag) {
            case Action::SHOW:
                ans.push_back(action.value);
                break;
            case Action::TRAVERSE:
                auto node = action.node;
                if (!node) continue;           // *
                tmp.push(Action{node->left});  // *
                tmp.push(Action{node->right}); // *
                tmp.push(Action{node->val});   // **
                break;
            }
            
            while (!tmp.empty())
                actions.push(tmp.top()), tmp.pop();
        }
        
        return ans;
    }
};

Note that I didn’t do the following:

actions.push(Action{node->left});  // *
actions.push(Action{node->right}); // *
ans.push_back(node->val)           // **

The problem with doing that is that it doesn’t accurately model our initial recursive form because the push_back statement, if placed somewhere else, would not be “deferred” in relation to the traversal steps.

What’s also nice about this approach is that, just like in the recursive form, we can trivially do pre-order and in-order traversals:

// pre-order
if (!node) continue;               // *
actions.push(Action{node->val});   // **
actions.push(Action{node->left});  // *
actions.push(Action{node->right}); // *

// in-order
if (!node) continue;               // *
actions.push(Action{node->left});  // *
actions.push(Action{node->val});   // **
actions.push(Action{node->right}); // *

Contrast that with some community solutions (e.g. this most voted one), which completely distort the underlying algorithm.

(Note: from this point on, I’m just playing around.)

Now, if we extract the traversal algorithm into its own function like so:

template <typename F>
void traverse(F&& f, TreeNode *node) {
    if (!node) return;      // *
    f(Action{node->left});  // *
    f(Action{node->right}); // *
    f(Action{node->val});   // **
}

Then, we can reuse it with either a recursive driver:

vector<int> recursively(TreeNode* root) {
    vector<int> ans;
    recursively_driver(ans, Action{root});
    return ans;
}

void recursively_driver(vector<int>& ans, Action action) {
    switch (action.tag) {
    case Action::SHOW:
        ans.push_back(action.value);
        break;
    case Action::TRAVERSE:
        traverse([&ans] (Action a) { recursively_driver(ans, a); }, action.node);
        break;
    }
}

or an iterative driver:

vector<int> iteratively(TreeNode* root) {
    vector<int> ans;
    
    stack<Action> actions;
    actions.push(Action{root});
    
    while (!actions.empty()) {
        auto action = actions.top();
        actions.pop();

        stack<Action> tmp;

        switch (action.tag) {
        case Action::SHOW:
            ans.push_back(action.value);
            break;
        case Action::TRAVERSE:
            traverse([&tmp] (Action a) { tmp.push(a); }, action.node);
            break;
        }

        while (!tmp.empty())
            actions.push(tmp.top()), tmp.pop();
    }
    
    return ans;
}

Lowest Common Ancestor of a Binary Search Tree

(Referring to this leetcode problem)

I opted for a (relatively) inefficient solution for the following reasons:

  • We don’t know whether this BST has any duplicate elements.
  • The required C++ function signature is (TreeNode* root, TreeNode* p, TreeNode* q). It could’ve been (TreeNode* root, int p, int q), for example. This fact, coupled with the previous point, suggests that object identity matters.

Moreover, consider the following tree:

        _______6______
       /              \
    _6(a)_          ___6__
   /      \        /      \
   6(p)   _6       6       6
         /  \
         6   6(q)

All nodes’ values are 6, yet we are passed p and q pointing to specific nodes. The answer in this case must be exactly a and not any other 6-valued node.

So, my algorithm consists of:

  1. Let p_path be the inclusive path from root to p, and similarly for q_path.
  2. The solution is the last element of the largest common prefix between p_path and q_path.

The (unoptimized) code:

class Solution {
public:
    TreeNode* lowestCommonAncestor(TreeNode* root, TreeNode* p, TreeNode* q) {
        auto p_path = findPath(root, p);
        auto q_path = findPath(root, q);
        
        assert(p_path.size() > 0);
        assert(q_path.size() > 0);
        assert(p_path[0] == root);
        assert(q_path[0] == root);
        assert(p_path.back() == p);
        assert(q_path.back() == q);
        
        int i = 1;
        for (; i < min(p_path.size(), q_path.size()); ++i) {
            if (p_path[i] != q_path[i]) {
                break;
            }
        }
        
        assert(p_path[i - 1] == q_path[i - 1]);
        
        return p_path[i - 1];
    }
    
    vector<TreeNode*> findPath(TreeNode* haystack, TreeNode* needle, vector<TreeNode*> path = {}) {
        path.push_back(haystack);
        if (needle->val < haystack->val)
            return findPath(haystack->left, needle, path);
        if (needle->val > haystack->val)
            return findPath(haystack->right, needle, path);
        // so, values are equal. we must explore all equal-value nodes
        path.pop_back(); // so we don't get dupes
        return findEq(haystack, needle, path);
    }
    
    vector<TreeNode*> findEq(TreeNode* haystack, TreeNode* needle, vector<TreeNode*> path = {}) {
        path.push_back(haystack);
        if (haystack == needle) {
            return path;
        }
        if (haystack->left && haystack->left->val == needle->val) {
            auto maybe = findEq(haystack->left, needle, path);
            if (!maybe.empty())
                return maybe;
        }
        if (haystack->right && haystack->right->val == needle->val) {
            auto maybe = findEq(haystack->right, needle, path);
            if (!maybe.empty())
                return maybe;
        }
        return {};
    }
};

Cardioid

Inspired by a YouTube video.

Link. Source code.

WebGL LCD Screen Burn-In "Fixer"

Whether this actually works or not, I can’t say for sure. The burn-in on my laptop’s LCD did disappear, though.

Click for fullscreen!

Link. Source code.

Inspired by this video.

Web Workers + Mandelbrot

Click to zoom!

Source available here.