Lowest Common Ancestor of a Binary Tree IV
J.P. Morgan
MicrosoftThe problem
Given the root of a binary tree and an array of TreeNodes objects nodes, return the** lowest common ancestor (LCA) **of all the nodes in nodes.
All the nodes will exist in the tree, and all values of the tree's nodes are unique.
The lowest common ancestor of n nodes p1,p2,...pn in a binary tree T is the lowest node that has every pi as a descendant (where we allow a node to be a descendant of itself) for every valid i. A descendant of a node x is a node y that is on the path from node x to some leaf node.
Input: root = [3,5,1,6,2,0,8,null,null,7,4], nodes = [4,7] Output: 2 **Explanation: ** The lowest common ancestor of nodes 4 and 7 is node 2.
**Input: **root = [3,5,1,6,2,0,8,null,null,7,4], nodes = [1] Output: 1 Explanation: The lowest common ancestor of a single node is the node itself.
**Input: **root = [3,5,1,6,2,0,8,null,null,7,4], nodes = [7,6,2,4]
- The number of nodes in the tree is in the range [1, 104].
- -109 <= Node.val <= 109
- All Node.val are unique.
- All nodes[i] will exist in the tree.
- All nodes[i] are distinct.
cpp
/**
* Definition for a binary tree node.
* class TreeNode {
* int data;
* TreeNode *left;
* TreeNode *right;
* TreeNode(int x) : data(x), left(NULL), right(NULL) {}
* };
*/
class Solution {
public:
TreeNode* lowestCommonAncestor(TreeNode* root, vector<TreeNode*> &nodes) {
//Your Code Goes Here
}
};java
/**
* Definition for a binary tree node.
* public class TreeNode {
* int data;
* TreeNode left;
* TreeNode right;
* TreeNode(int x) { data = x; }
* }
*/
class Solution {
public TreeNode lowestCommonAncestor(TreeNode root, List<TreeNode> nodes) {
// 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
class Solution:
def lowestCommonAncestor(self, root, nodes):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;
* }
* }
**/
class Solution {
lowestCommonAncestor(root,nodes) {
//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(int val) { data = val; }
* }
*/
public class Solution {
public TreeNode LowestCommonAncestor(TreeNode root, List<TreeNode> nodes) {
// Your Code Goes Here
}
}go
func lowestCommonAncestor(root *TreeNode, nodes []*TreeNode) *TreeNode {
// Your code goes here
}Stuck? Show a way to structure it+
- 01Put all target-node references in a set.
- 02Run postorder DFS.
- 03Return a target immediately when encountered.
- 04If two child calls are non-null, return the current node.
- 05Otherwise propagate the non-null child result.
Reference answer
Then expect these follow-ups
How would you validate that every requested node occurs?
Tests: robustness
Can this be iterative?
Tests: parent maps
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