Lowest Common Ancestor of Deepest Leaves - Leetcode 1123 - Python

0:00 - Read the problem
2:30 - Drawing Explanation
15:00 - Coding Explanation
17:45 - Coding Explanation 2

leetcode 1123

#neetcode #leetcode #python

[reomurphy]

Went with BFS solution, found it rather intuitive
Have a Triplet class with Parent, Node, Depth as variables.
Using a Map to find every node's parent.

Using a Queue (Level order traversal) to find left most and right most leaf node at max depth.
Using a Priority Queue to get only max depth nodes
If just one node -> return the node itself
If 2 nodes (At max can have 2 nodes only (left most and right most)) -> search their parents until they're same


class Solution {
public TreeNode lcaDeepestLeaves(TreeNode root) {

Map<TreeNode, TreeNode> map = new HashMap<>();
Queue<Pair> q = new LinkedList<>();
PriorityQueue<Pair> pq = new PriorityQueue<>((p1, p2) -> Integer.compare(p2.depth, p1.depth));

q.add(new Pair(root, root, 0));

int max = 0;

while(!q.isEmpty()) {
int n = q.size();

for(int i=0; i<n; i++) {
Pair p = q.poll();

map.put(p.node, p.parent);

if(p.node.left == null && p.node.right == null) {
if(i == 0 || i == n-1) {
pq.add(p);
max = Math.max(max, p.depth);
}
}

if(p.node.left != null) {
q.add(new Pair(p.node, p.node.left, p.depth+1));
}

if(p.node.right != null) {
q.add(new Pair(p.node, p.node.right, p.depth+1));
}
}
}

List<Pair> list = new ArrayList<>();

while(!pq.isEmpty() && pq.peek().depth == max) {
list.add(pq.poll());
}

if(list.size() == 1) return list.get(0).node;

TreeNode p1 = list.get(0).node;
TreeNode p2 = list.get(1).node;

while(true) {
if(map.get(p1) == map.get(p2)) break;

p1 = map.get(p1);
p2 = map.get(p2);
}

return map.get(p1);
}
}

class Pair {

TreeNode parent;
TreeNode node;
int depth;

public Pair(TreeNode p, TreeNode n, int d) {
this.parent = p;
this.node = n;
this.depth = d;
}
}

Accepted.

[chrischika]

Although longer I think the BFS + LCA Solution is better and more understandable.
Here's my code
class Solution:
def lcaDeepestLeaves(self, root: Optional[TreeNode]) -> Optional[TreeNode]:
queue = deque([root])
while queue:
deepest = []
for _ in range(len(queue)):
node = queue.popleft()
deepest.append(node)
if node.left:
queue.append(node.left)
if node.right:
queue.append(node.right)

def lca(root):
if not root:
return None
if root.val == deepest[0].val or root.val == deepest[-1].val:
return root
left, right = lca(root.left), lca(root.right)
if left and right:
return root
return left or right
return lca(root)

[_id_]

If anyone asks, the method of maintaining a vector<pair<TreeNode*, int>> which contains all deepest nodes, has a 30% memory usage, despite 100% on runtime.

[thesun]

To people having trouble understanding (like me), whenever he mentions common ancestor; think of it as a node that has subtrees of same height instead of ancestor of some arbitrary two nodes like the actual lca question.
Using this approach i got 1ms on TreeNode[] and 0ms on a custom class. Thanks NeetCode.

[ZORO__OP]

for some reason i could not understand the problem statement, whatr it was asking to do? But once you explained it, i could code it up.

[hymnes-orphiques]

Yesterday I solved a hard with an acceptance rate of 42% all by myself, this morning this medium with a >70% acceptance rate kicked my ass hard.
I'm tired boss.

[tanzeembelal]

I was able to solve it by preprocessing the height of the tree -1 as levels and regular dfs to find lca and whenever a leaf node is encountered I would check the current level if its 0 then its the deepest leaf and would return the node and rest of the logic for LCA is same.

[ZMan-lxpg]

Why do you have so less views? Your explanation is brilliant!

[oogieboogie]

DFS with one return value and a global reference

class Solution:
def lcaDeepestLeaves(self, root: Optional[TreeNode]) -> Optional[TreeNode]:
self.res = root
self.maxDepth = 0
def dfs(node, depth):
if not node:
return depth-1
leftDepth = dfs(node.left, depth+1)
rightDepth = dfs(node.right, depth+1)
if leftDepth == rightDepth and leftDepth >= self.maxDepth:
self.res = node
self.maxDepth = leftDepth
return max(leftDepth, rightDepth)
dfs(root, 1)
return self.res

[floatingpoint]

i prefer the first approach which returns multiple values, its moe easy to understand

[raamkishorep]

Line 13, depth+1 is not needed and intuitively, it's kinda incorrect I guess. More likely, it has to be depth-1 (since the None stuff shouldn't even be considered as a depth). I have already ran the code and it's passing.

[josephsamuelm]

Hi @NeetCodeIO, could you also share similar problems to help us get better at this pattern?

[DBagg-zzip]

My guess before watching: Bfs to last level to get set of lowest leaves, then bfs from them back up until one node is left.
…
Ohhhh didn’t think of that

[TheSocialDeveloper]

Bro is dangerous. I figured it was bottom up, but couldn't solve it that way so I did some python magic.

class Solution:
def __init__(self):
self.depth = 0
self.paths = []

def dfs(self, node, depth, path):
if not node:
return

path = path + [node]

if depth > self.depth:
self.paths = [path]
self.depth = max(depth, self.depth)
elif depth == self.depth:
self.paths.append(path)


self.dfs(node.left, depth + 1, path)
self.dfs(node.right, depth + 1, path)

def lcaDeepestLeaves(self, root: Optional[TreeNode]) -> Optional[TreeNode]:
self.ancestor = root

self.dfs(root, 0, [])

common = None
for i in range(len(self.paths)):
if common:
common = [x for x in common if x in set(self.paths[i])]
else:
common = self.paths[i]

self.ancestor = common[-1]

return self.ancestor

Forgive me, but I needed to solve it

[araneuskyuro]

I'm still confused as to why we do DFS. Wouldn't BFS have a better runtime?

[saruhasan]

# Definition for a binary tree node.
# class TreeNode:
# def __init__(self, val=0, left=None, right=None):
# self.val = val
# self.left = left
# self.right = right
class Solution:
def lcaDeepestLeaves(self, root: Optional[TreeNode]) -> Optional[TreeNode]:
def findDepth(crt, depth):
if crt == None:
return depth
return max(findDepth(crt.left, depth + 1), findDepth(crt.right, depth + 1))
depth = findDepth(root, 0)

res = None

def dfs(crt, curr_depth):
nonlocal res
if crt == None:
return curr_depth
left_dth = dfs(crt.left, curr_depth + 1)
right_dth = dfs(crt.right, curr_depth + 1)
if left_dth == depth and right_dth == depth:
res = crt
return max(left_dth, right_dth)
dfs(root, 0)

return res

Can you explain why this works, I thought we need to take min depth of left and right sub tree, but that didn't work, then when I changed to max it works

[vandit_quantum]

How did you figure out it was returning the tree... I did not even understand the problem just because of that... were you stuck too ?

[vuejs]

Is it ok, if I can solve medium difficulty questions but I make mistakes constantly. =(
Like small stupid mistakes, so I can't solve it on a first try? Even if I have solved same question before?