88. LCA in BT

Given a root of binary tree, find the lowest common ancestor (LCA) of two given nodes (p, q) in the tree.

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

Note: Return the TreeNode itself, not its value.

Example 1:

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

Output : 3

Explanation :

Example 2:

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

Output : 5

Explanation :

Now Your Turn!

Pick the correct output for the given input

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

Still unsure what the problem is asking ?

Let’s go through a few more examples, step by step, to make it clearer.

Constraints:

  • 2 <= Number of Nodes <= 105
  • -106 <= node.val <= 106
  • All values in tree are unique.

Hints

Frequently Occurring Doubts

Interview Follow-up Questions

Fun Facts

0
/**
* Definition for a binary tree node.
* struct TreeNode {
* int data;
* TreeNode *left;
* TreeNode *right;
* TreeNode(int val) : data(val) , left(nullptr) , right(nullptr) {}
* };
**/
 
class Solution {
public:
TreeNode* lowestCommonAncestor(TreeNode* root, TreeNode* p, TreeNode* q) {
//your code goes here
}
};
Test Case

Input:

P
Q
Root
to save your code