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;
}

Related

How to 10x Your LLM Prompting With DSPy

Tired of spending countless hours tweaking prompts for large...

Google Announces A Cost Effective Gemini Flash

At Google's I/O event, the company unveiled Gemini Flash,...

WordPress vs Strapi: Choosing the Right CMS for Your Needs

With the growing popularity of headless CMS solutions, developers...

JPA vs. JDBC: Comparing the two DB APIs

Introduction The eternal battle rages on between two warring database...

Meta Introduces V-JEPA

The V-JEPA model, proposed by Yann LeCun, is a...

Subscribe to our AI newsletter. Get the latest on news, models, open source and trends.
Don't worry, we won't spam. 😎

You have successfully subscribed to the newsletter

There was an error while trying to send your request. Please try again.

Lusera will use the information you provide on this form to be in touch with you and to provide updates and marketing.