Solving Leetcode 236. Lowest Common Ancestor of a Binary Tree

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).”

Explaining Leetcode 236

To solve the problem of finding the lowest common ancestor (LCA) of a binary tree, you can use a recursive approach. The basic idea is to recurse down the tree and at each node, check if the given nodes p and q are on the left or right subtree. If one of the nodes is on one side and the other is on the other side, then the current node is the LCA. Otherwise, if both nodes are on the left or right subtree, then recurse down that subtree to continue searching for the LCA.

It is difficult to provide a diagram for the problem of finding the lowest common ancestor (LCA) of a binary tree, as the tree can have any number of nodes and any structure. However, here is a general diagram showing the concept of an LCA in a binary tree:

     A
   /   \
  B     C
 / \   / \
D   E F   G
   /   \
  H     I

In this example, the LCA of nodes H and I is node E. The LCA of nodes D and I is node A, and the LCA of nodes A and C is also node A.

To find the LCA of two nodes in a binary tree, you can use a recursive or iterative approach, as discussed in the previous answer. The specific algorithm will depend on the structure of the tree and the positions of the given nodes.

Solution

There are two main ways to solve the problem of finding the lowest common ancestor (LCA) of a binary tree: using a recursive approach, or using an iterative approach.

The recursive approach involves defining a recursive function that takes the current node, and the two nodes for which we want to find the LCA. At each step, the function checks if the given nodes are on the left or right subtree of the current node. If one of the nodes is on one side and the other is on the other side, then the current node is the LCA. Otherwise, if both nodes are on the left or right subtree, then the function recursively searches for the LCA in that subtree.

The iterative approach, on the other hand, involves using a stack to store the nodes that we have visited while traversing the tree. We then iterate over the stack to find the first node that has the given nodes in its left and right subtrees, respectively. This node is the LCA.

Both of these approaches have the same time and space complexity, which is O(n) in the worst case, where n is the number of nodes in the tree. The choice of which approach to use will depend on the specific needs of your implementation and your personal preference.

You can also use an iterative approach to solve this problem. In this case, you would use a stack to store the nodes that you have visited while traversing the tree. You would then iterate over the stack to find the first node that has p and q in its left and right subtrees, respectively. This node would be the LCA.

For our purpose we will be using the recursive version.

Solving in JavaScript:

const lowestCommonAncestor = (root, p, q) => {
  if (root === null || root === p || root === q) return root;
  let left = lowestCommonAncestor(root.left, p, q);
  let right = lowestCommonAncestor(root.right, p, q);
  if (left && right) return root;
  return left ? left : right;
};

Solving in TypeScript:

function lowestCommonAncestor(
  root: TreeNode | null,
  p: TreeNode | null,
  q: TreeNode | null
): TreeNode | null {
  if (root === null || root === p || root === q) return root;
  let left = lowestCommonAncestor(root.left, p, q);
  let right = lowestCommonAncestor(root.right, p, q);
  if (left && right) return root;
  return left ? left : right;
}

Solving in Java:

public TreeNode lowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q) {
      if (root == null) return null;
      if (root.val == p.val || root.val == q.val) return root;
      TreeNode left = lowestCommonAncestor(root.left, p, q);
      TreeNode right = lowestCommonAncestor(root.right, p, q);
      if (left != null && right != null) return root;
      if (left == null && right == null) return null;
      return left != null ? left : right;
}