• 29.6%

https://leetcode.com/problems/lowest-common-ancestor-of-a-binary-tree/#/description

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 v and w as the lowest node in T that has both v and w as descendants (where we allow a node to be a descendant of itself).”

For example, the lowest common ancestor (LCA) of nodes 5 and 1 is 3. Another example is LCA of nodes 5 and 4 is 5, since a node can be a descendant of itself according to the LCA definition.

Dec 10th, 2017

http://www.geeksforgeeks.org/lowest-common-ancestor-binary-tree-set-1/

https://discuss.leetcode.com/topic/18561/4-lines-c-java-python-ruby

4 lines C++/Java/Python/Ruby

Same solution in several languages. It’s recursive and expands the meaning of the function. If the current (sub)tree contains both p and q, then the function result is their LCA. If only one of them is in that subtree, then the result is that one of them. If neither are in that subtree, the result is null/None/nil.

Update: I also wrote two iterative solutions now, one of them being a version of the solution here. They’re more complicated than this simple recursive solution, but I do find them interesting.

C++

Python

Or using that None is considered smaller than any node:

Ruby

Java

https://discuss.leetcode.com/topic/27479/java-python-iterative-solution

Java/Python iterative solution

Python

Java

To find the lowest common ancestor, we need to find where is p and q and a way to track their ancestors. A parent pointer for each node found is good for the job. After we found both p and q, we create a set of p’s ancestors. Then we travel through q’s ancestors, the first one appears in p’s is our answer.

https://discuss.leetcode.com/topic/18652/iterative-solutions-in-python-c

Iterative Solutions in Python/C++

Solution 1

Same algorithm as my recursive solution (look there if you want some explanation), but iterative. I do a post-order traversal with a stack. Each stack element at first is a [node, parent] pair, where parent is the stack element of the node’s parent node. When the children of a parent get finished, their results are appended to their parent’s stack element. So when a parent gets finished, we have the results of its children/subtrees available (its stack element at that point is [node, parent, resultForLeftSubtree, resultForRightSubtree]).

Solution 2

Here I find the paths to p and q and then find the last node where the paths match. I just came up with the path-building technique for this, and I find it quite neat and maybe it could be useful elsewhere.

C++ version of Solution 1

I don’t use C++ much, so maybe there’s room for improvement with stuff that I don’t know.

https://discuss.leetcode.com/topic/20063/accepted-24ms-dfs-c-solution-only-3-lines

Accepted 24ms DFS c++ solution, only 3 lines.

https://discuss.leetcode.com/topic/18786/very-simple-dfs-c-solution-only-10-lines

Very simple dfs c++ solution , only 10 lines

https://discuss.leetcode.com/topic/26396/short-and-clean-c-solution

Short and clean C++ solution

Want to share my solution.