Lowest Common Ancestor of a Binary Tree III
Amazon
LinkedinThe problem
Given two nodes of a binary tree p and q, return their lowest common ancestor (LCA).
Each node will have a reference to its parent node. The definition for is below
class TreeNode { public int val; public TreeNode left; public TreeNode right; public TreeNode parent; }
The lowest common ancestor of two nodes p and q in a tree T is the lowest node that has both p and q as descendants (where we allow a node to be a descendant of itself).
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.
Input: root = [3,5,1,6,2,0,8,null,null,7,4], p = 5, q = 4 Output: 5 Explanation: The LCA of nodes 5 and 4 is 5 since a node can be a descendant of itself according to the LCA definition.
Input: root = [1,2], p = 1, q = 2
- The number of nodes in the tree is in the range [2, 105].
- -109 <= Node.val <= 109
- All Node.val are unique.
- p != q
- p and q exist in the tree.
cpp
/*
// Definition for a Node.
class TreeNode {
public:
int data;
TreeNode* left;
TreeNode* right;
TreeNode* parent;
};
*/
class Solution {
public:
TreeNode* lowestCommonAncestor(TreeNode* p, TreeNode* q) {
}
};java
/**
* Definition for a binary tree node.
* public class TreeNode {
* int data;
* TreeNode left;
* TreeNode right;
* TreeNode parent;
* TreeNode(int x) { data = x; }
* }
*/
class Solution {
public TreeNode lowestCommonAncestor(TreeNode p, TreeNode q) {
// Your Code Goes Here
}
}python
# Definition for a binary tree node.
# class TreeNode(object):
# def __init__(self, x):
# self.data = x
# self.left = None
# self.right = None
# self.parent = None
class Solution:
def lowestCommonAncestor(self, p, q):javascript
/**
* Definition for a binary tree node.
* class TreeNode {
* constructor(data = 0, left = null, right = null){
* this.data = data;
* this.left = null;
* this.right = null;
* this.parent = null;
* }
* }
**/
class Solution {
lowestCommonAncestor(p,q) {
//your code goes here
}
}csharp
/**
* Definition for a binary tree node.
* public class TreeNode {
* public int data;
* public TreeNode left;
* public TreeNode right;
* public TreeNode parent;
* TreeNode(int x) { data = x; }
* }
*/
public class Solution {
public TreeNode lowestCommonAncestor(TreeNode p, TreeNode q) {
// Your Code Goes Here
}
}go
func lowestCommonAncestor(p, q *TreeNode) *TreeNode {
// Your code goes here
}Stuck? Show a way to structure it+
- 01Start one pointer at each node.
- 02Move each pointer to its parent on every step.
- 03When a pointer reaches null, redirect it to the other start node.
- 04Stop when pointers meet.
- 05Return the meeting node or null.
Reference answer
Then expect these follow-ups
What hash-set alternative would you use?
Tests: tradeoffs
How would you solve it without parent pointers?
Tests: tree traversal
Free to read · better with Enzo
Practice this out loud with Enzo
Enzo runs it as a mock interview, pushes back with follow-ups, and grades you on the rubric.
Next question