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.