Lowest Common Ancestor Of A Binary Tree Iii - Leetcode Solution

Problem Statement:

Given two nodes in a binary tree, find their lowest common ancestor (LCA).

The lowest common ancestor is the node with the largest depth which is the ancestor of both nodes.

Assume that the two nodes are always present in the binary tree.

Example:

Input: root = [3,5,1,6,2,0,8,null,null,7,4], p = 5, q = 1

Output: 3

Explanation: The LCA of nodes 5 and 1 is 3.

Solution:

Approach:

The approach we will follow here is quite simple. We will use depth first search (DFS) to traverse the binary tree.

We will follow the below steps to solve the problem:

1. Initialize two variables - depth and parent, and initialise these to null.

2. Now, we traverse the tree and look for p and q nodes.

3. For each node we visit, we will check if it matches with either p or q. If so, we set the parent variable for that node.

4. We also set the depth for each node with the help of a counter variable.

5. After we have found both p and q nodes, we traverse back up, and at each level we compare the parent nodes of p and q to see if they match. If they do, we return that node as LCA.

6. Otherwise, we continue traversing up.

Code:

Here is the code for Lowest Common Ancestor of a Binary Tree III problem on leetcode:

/**

• 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: TreeNode lowestCommonAncestor(TreeNode* root, TreeNode* p, TreeNode* q) { pair<TreeNode*, int> ans1 = dfs(root, p, NULL, 0); pair<TreeNode*, int> ans2 = dfs(root, q, NULL, 0);

   if (ans1.second < ans2.second)
       q = climbUp(q, ans2.second - ans1.second);
   else if (ans1.second > ans2.second)
       p = climbUp(p, ans1.second - ans2.second);
  
   while (p != q) {
       p = p->parent;
       q = q->parent;
   }
  
   return p;
  

  }

  // Returns the node and its depth in the tree. pair<TreeNode*, int> dfs(TreeNode* node, TreeNode* target, TreeNode* parent, int depth) { if (!node) return { NULL, -1 }; if (node == target) return { parent, depth }; auto left = dfs(node->left, target, node, depth + 1); auto right = dfs(node->right, target, node, depth + 1); return (left.first ? left : right); }

  TreeNode* climbUp(TreeNode* node, int delta) { while (delta--) node = node->parent; return node; } };

Complexity Analysis:

Time Complexity: O(n), where n is the number of nodes in the binary tree.

Space Complexity: O(h), where h is the height of the binary tree. The space required in recursion stack is as large as the height of binary tree.

1