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

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 first version.
My final version can be found here.

This version my thought lets brute force this to see if I can do it.

/**
 * 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:
    bool findPath(TreeNode* root, TreeNode* dst, std::vector<TreeNode*>& path) {
        if (root == nullptr) {
            return false;
        }

        path.push_back(root);
        if (root == dst) {
            return true;
        }
        if (findPath(root->left, dst, path)) {
            return true;
        }
        if (findPath(root->right, dst, path)) {
            return true;
        }
        path.pop_back();
        return false;
    }
    TreeNode* lowestCommonAncestor(TreeNode* root, TreeNode* p, TreeNode* q) {

        std::vector<TreeNode*>   pPath;
        findPath(root, p, pPath);
        //std::cout << "pSize: " << pPath.size() << "\n";

        std::vector<TreeNode*>   qPath;
        findPath(root, q, qPath);
        //std::cout << "qSize: " << qPath.size() << "\n";

        TreeNode* best = root;
        for (std::size_t loop = 0; true; ++loop) {
            if (loop >= pPath.size() || loop >= qPath.size()) {
                //std::cout << "Loop: " << loop << "\n";
                break;
            }
            //std::cout << "L: " << loop << " p: " << pPath[loop]->val << " q: " << qPath[loop]->val << "\n";
            if (pPath[loop] != qPath[loop]) {
                break;
            }
            best = pPath[loop];
        }
        return best;
    }
};

Answer 1

This is obviously not an optimal solution.

From the question:

The number of nodes in the tree is in the range [2, 10^5].

So in the worst case scenario we could have a linked list of 1,000,000 nodes. This could in the worst case result in both qPath and pPath being vectors of 1,000,000 items that need to be compared.

So it has a very horrible worst case, especially since this is not a balanced tree.

---

The other issue is that we can scan the tree twice. Once for p and once for q. It would be better to only scan the tree only once.

---

Rather than use a manual comparison of the two vectors. There is a standard algorithm for comparing two ranges.

std::mismatch

---

Not sure what the default capacity of a vector is. But potentially we could do some reserving to try and minimize the number of reallocations that could happen. Some happy approximation of 100 seems resonable approximation that could be tried. if ln(1,000,000) == 22 Then we can easily see a reasonably balanced tree getting to 100.

Answer 2

Since you know you want to find exactly two paths, you could create a special-purpose findPath() that traverses the tree once and populates both paths.

Answer 3

I know you have another version that implements a different algorithm, so I won't discuss the choice of algorithm itself.

Simplify lowestCommonAncestor()

It would be nice if this function could be simplified even more, show just the high level steps necessary to get to the solution. Using std::mismatch() would already replace a lot of the code. Another thing that could be done is make findPath() return the path as a return value. That way, the function could be written as:

TreeNode* lowestCommonAncestor(TreeNode* root, TreeNode* p, TreeNode* q) {
    auto pPath = findPath(root, p);
    auto qPath = findPath(root, q);
    auto highestUncommonAncestors = std::ranges::mismatch(pPath, qPath);
    return *std::prev(highestUncommonAncestors.in1);
}

A cleaner findPath()

Clearly you have written findPath() with performance in mind; you wanted to avoid allocating multiple vectors from the outset, so you declare the vector outside findPath() and just pass a reference to it. But is that really necessary? Let's write it first in a more functional style:

using Path = std::deque<TreeNode*>;

Path findPath(TreeNode* root, TreeNode* dst) {
    if (!root) {
        return {};
    }

    if (root == dst) {
        return {dst};
    }

    Path path = findPath(root->left, dst);
    if (rest_of_path.empty())
        path = findPath(root->right, dst);

    if (!rest_of_path.empty())
        path.push_front(root);

    return path;
}

I used a std::deque here to ensure we can .push_front() efficiently, but you could also use a std::vector and .push_back(), but then you'd have to reverse the path afterwards, or use reverse iterators for std::mismatch().

It might look inefficient, but RVO and move assignment should avoid making copies of non-empty paths, and empty paths shouldn't cause any memory allocations to happen.

Consider repurposing val

struct TreeNode has a member variable val, but it is not used in the algorithm. Maybe LeetCode doesn't care about it either? In this case, you can repurpose it. When visiting nodes the first time, set val to zero. Then if you have found the destination node and start unwinding the recursion, set bit 0 if you need to follow the left child to get to the destination, and set bit 1 if you need to follow the right child. Then, instead of using std::mismatch(), you start at the root and follow either the left or right child depending on which bit is set. If you hit a node that has both bits set, you know that that is the lowest common ancestor.

Some details might have to be sorted out first, like how to zero val first. But it avoids having to store any extra information.

About the worst case scenario

In the worst case scenario we could have a linked list of 1,000,000 nodes. This could in the worst case result in both qPath and pPath being vectors of 1,000,000 items that need to be compared.

But you would have had a recursion depth of 1,000,000 then anyway, even in your improved version. I would be more worried about stack overflow in that case.

In this case, you could consider using a form of path compression: if you see a TreeNode with only one child, and the child is neither p nor q, you can replace the parent's child pointers with its grandchildren. You could do this in a while-loop so the path compression itself doesn't cause excessive stack usage.