Leetcode.com problem 236: "Lowest Common Ancestor of a Binary Tree"

James S. Plank

• Problem Statement.
• Medium problem
• Success Rate (as of July, 2022): 57.2%

Suppose we want to find the lowest common ancestor of 4 and 6. Obviously, when we eyeball the tree, it's easy to see it is node 5. However, since we are only given the root of the tree and the two nodes, which don't have parent pointers, we need to do some traversal of the tree, from the root, to find these nodes and discover their least common ancestor.

Here's the strategy that I took -- do a postorder tree traversal, and label each node with two bits. Let's call them PQ. We set bit P if a node is an ancestor of node p and bit Q if a node is an ancestor of node q. Here's the labeling of the example tree with p = 4 and q = 6:

I'm hoping you can see how you make this work with a postorder traversal. You want to find the lowest node in the tree whose bits are "11". If you're doing a postorder traversal, this will happen the first time that you see a node whose bits are 11.

Here's my code. It's not a classic postorder traversal, because I stop after visiting the left subtree if I've determined that this is the lowest common ancestor. This code was faster than 95.5% of the C++ submissions, and used less memory than 85%. Obviously, I don't know why, but I'm guessing that other solutions did something like:

• Find P with a DFS and store all of its ancestors in a vector.
• Find Q with a DFS and store all of its ancestors in a vector.
• Figure out the lowest common ancestor from the vector.

(In solution.cpp):

#include <string>
#include <vector>
#include <list>
#include <cmath>
#include <algorithm>
#include <map>
#include <set>
#include <iostream>
#include <sstream>
#include <cstdio>
#include <cstdlib>
using namespace std;

class Solution {
public:
    TreeNode* lowestCommonAncestor(TreeNode* root, TreeNode* p, TreeNode* q);
    TreeNode *P, *Q, *LCA;
    int postorder(TreeNode *n);
};

/* This returns the pq bits of node n. */

int Solution::postorder(TreeNode *n)
{
  int anc;

  if (n == nullptr) return 0;
  anc = 0;

  if (n == P) anc |= 1;     // If the node is p or q, then set the proper bit.
  if (n == Q) anc |= 2;

  // Call postorder on the left child, and then OR in the bits.  If both are set, then
  // this is the lowest common ancestor -- return it.

  if (n->left != NULL) anc |= postorder(n->left);
  if (anc == 3 && LCA == NULL) {
    LCA = n;
    return 3;
  }

  // Call postorder on the right child, and do the same thing that you did with the left child.

  if (n->right != NULL) anc |= postorder(n->right);
  if (anc == 3 && LCA == NULL) {
    LCA = n;
    return 3;
  }

  return anc;
}

TreeNode* Solution::lowestCommonAncestor(TreeNode* root, TreeNode* p, TreeNode* q)
{
  P = p;
  Q = q;
  LCA = NULL;
  postorder(root);
  return LCA;
}