Leet Code: 236. Lowest Common Ancestor of a Binary Tree

Question

Trying my hand at Leet 236.

Given a binary tree, find the lowest common ancestor (LCA) of two given nodes in the tree.

According to the definition of LCA on Wikipedia: “The lowest common ancestor is defined between two nodes p and q as the lowest node in T that has both p and q as descendants (where we allow a node to be a descendant of itself).”

This is the final version.
My first version can be found here.

/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode(int x) : val(x), left(NULL), right(NULL) {}
 * };
 */
class Solution {
public:
    // So if we can find `q` in the subtree routed by c
    bool match(TreeNode* c, TreeNode* q)
    {
        // recursive out
        if (c == nullptr) {
            return false;
        }
        // We found it.
        if (c == q) {
            return true;
        }

        // Search left and right.
        // Note: The '||' is shortcut operator. So if we find in the left
        //       we don't search the right.
        return match(c->left, q) || match(c->right, q);
    }
    TreeNode* lca(bool& found, TreeNode* c, TreeNode*& p, TreeNode*& q)
    {
        // recursive out.
        if (c == nullptr) {
            return nullptr;
        }

        // See if the current node is p or q.
        if (c == p) {
            found = true;
        }
        else if (c == q) {
            // If it is q then swap p and q.
            // This makes it easy to know what to pass to match()
            // We will always pass q.
            std::swap(p, q);
            found = true;
        }

        // Note: If we have found one then found is true and the other is in q.
        TreeNode* find = found
            // We have found one. See if the other is the left subtree.
            // If so then c is the lca.
            ? (match(c->left, q) ? c : nullptr)
            // We have not found either. So recursively try again.
            : lca(found, c->left, p, q);

        // Only need to search the right tree if nothing was found in the left.
        if (find == nullptr) {
            find = found
                // We have found one. See if the other is the right subtree.
                // If so then c is the lca.
                ? (match(c->right, q) ? c : nullptr)
                // We have not found either. So recursively try again.
                : lca(found, c->right, p, q);
        }
        // Note this may be nullptr
        return find;
    }
    TreeNode* lowestCommonAncestor(TreeNode* root, TreeNode* p, TreeNode* q)
    {
        // Optimization.
        // If either node is root then this is the common ancestor
        // as we know the other node must exist and thus be in one of
        // the branches.
        if (root == p || root == q) {
            return root;
        }

        bool found = false;
        // Search left branch.
        TreeNode* find = lca(found, root->left, p, q);

        // If LCA was not found the search the right.
        if (!find) {
            // Optimization.
            // If we found either of p or q in the left, but not
            // the other one. Then we know the other one must be
            // in the right branch. Thus we don't need to search
            // the right branch.
            find = found ? root : lca(found, root->right, p, q);
        }
        return find;
    }
};

Answer 1

Naming things

The names you are using are confusing. match() should rather be contains(). lca() is the acronym of lowestCommonAncestor(), but the former is just a helper function for the full LCA algorithm. So maybe lca_helper() would be better? find and found in the same function is also very confusing. I would also avoid using names that are also used in the STL for commonly used things (like std::find()). A better name for find might be ancestor.

The variable names p and q are excusable; I wouldn't know what else to call them, and something like node1 and node2 doesn't sound much more informative. But instead of c, consider writing subtree or subroot.

Simplify lowestCommonAncestor()

It looks to me like lowestCommonAncestor() just unrolls the first level of the search unnecessarily, and you can just replace it with:

TreeNode* lowestCommonAncestor(TreeNode* root, TreeNode* p, TreeNode* q)
{
    bool found = false;
    return lca(found, root, p, q);
}

Avoid code duplication

Inside lowestCommonAncestor() there is also some code duplication going on. You can avoid this by writing something like this:

TreeNode *ancestor = nullptr;

for (auto child: {subtree->left, subtree->right}) {
    if (!ancestor) {
        ancestor = found
                   ? (contains(child, q) ? subtree : nullptr)
                   : lca_helper(found, child, p, q);
    }
}

About class Solution

As Toby also mentioned: while the structure of the code might be dictated by the LeetCode website, in production code you would not use a class at all, but rather just write a stand-alone function to find the common ancestor. The helper functions could then either be put in an anonymous namespace, or declared as lambdas inside lowestCommonAncestor().

Furthermore, you could write a generic function, templated on the type of tree node, so it would work with a greater variety of tree types. One might also consider using a graph library like Boost::Graph.

Answer 2

Code Structure

It's not mentioned in the question, but I'm guessing that class Solution is something that's required by the challenge. I'd be surprised to find that those three public member functions are required, though - surely it's possible to make one or more of them private?

Since none of the functions use any of the data of Solution, they should probably be static, or (better), free functions in an anonymous namespace.

Data structure

A tree node with pointer to parent will make for a much more efficient bottom-up search, and the extra size of the node may well be worth the payback in execution time. But perhaps this is imposed by the challenge too? (I tried following your link, but it just leads to an empty HTML)

If we're constrained to working with trees that have no parent link, we can make good use of some auxiliary storage to store the paths from root to each of the target nodes. Then we can use a simple std::mismatch to locate where those paths differ.

Recursion

One of the answers to the linked question claims that the tree may have as many as 10⁵ nodes. If it's completely balanced, that implies a depth of up to 17 levels. But if it's not balanced, we could be recursing 10⁵ times, which will exceed execution limits on many platforms. We might need to transform to a more iterative solution, keeping state in allocated memory rather than on the call stack.

Redundant output

I may be mistaken, but it appears that lca() sets found exactly when its return value is not null.

Minor

It's worth using correct spelling, even in comments - in larger codebases, it can make it easier to search for things you remember writing, and in any case it helps reassure readers that you have taken reasonable care writing your code:

    // See if we can find 'q' in the subtree rooted at 'c'
    // 🔺🔺🔺                                 🔺🔺🔺🔺🔺🔺