LeetCode 236. Lowest Common Ancestor of a Binary Tree - Backtracking Solution - Python

Question

I am working on this question (https://leetcode.com/problems/lowest-common-ancestor-of-a-binary-tree/) and I tried to solve it with backtracking in python, here is my logic:

Traverse through the tree and find both of the nodes
return their path, and then find the first element that appears in both path and it would be the LCA

Here is my code:

class Solution:
    def lowestCommonAncestor(self, root: 'TreeNode', p: 'TreeNode', q: 'TreeNode') -> 'TreeNode':
        self.path_1 = []
        self.path_2 = []
        
        self.traverse(root, [], p, q)
        
        print(self.path_1, self.path_2)
        
        for val in self.path_1:
            if val in self.path_2:
                return val
        
    def traverse(self, node, path, p, q):
        if not node:
            return
        
        path.append(node.val)
        
        if node is p:
            self.path_1 = path
        
        if node is q:
            self.path_2 = path
        
        self.traverse(node.left, path, p, q)
        self.traverse(node.right, path, p, q)
        path.remove(node.val)

It seems the backtracking part does not work and it does not give me the path to both nodes. Can someone help me troubleshoot how to fix this method? I know this solution isn't the most optimal way to solve this question, but I wanted to know what is wrong with my logical thoughts in code. Thanks upfront!

score 0 · Answer 1 · answered Feb 07 '23 at 21:07

There was only a few logic mistakes that I found. Other than that the big problem was more of a programming concept.

Logic Mistakes

You want to keep track of the nodes, not the values. This is because when the answer expects a Node not a value.
You want to iterate in the reverse order. Since we're using a list to keep track of the paths that means that the first element we add is the root. The root will always be an ancestor but it will not always be the lowest ancestor. Traverse the paths in reverse to find out the lowest.

Other than that the only thing missing was the fact that you need to create a copy of the path. A shallow copy works fine in this case. As your program works on things recursively we know that the path changes, when we want to save the path in the path_1 and path_2 we want a snapshot of the path by copying the current snapshot of path.

"Shallow copying, a and b will become two isolated objects, but their contents still share the same reference[1]". By isolating the variables we fix the big problem. Since the contents of the path are TreeNode's that means they are references to objects. Since our algorithm never changes these Node's having a reference to these Nodes are fine.

class Solution:
    def lowestCommonAncestor(self, root: 'TreeNode', p: 'TreeNode', q: 'TreeNode') -> 'TreeNode':
        self.path_1 = []
        self.path_2 = []
        
        self.traverse(root, [], p, q)
        
        for node in reversed(self.path_1):
            if node in reversed(self.path_2):
                return node
        return root
        
    def traverse(self, node, path, p, q):
        if not node:
            return
        
        path.append(node)
        
        if node.val == p.val:
            self.path_1 = path.copy()
        
        if node.val == q.val:
            self.path_2 = path.copy()
        
        self.traverse(node.left, path, p, q)
        self.traverse(node.right, path, p, q)
        path.remove(node)

LeetCode 236. Lowest Common Ancestor of a Binary Tree - Backtracking Solution - Python

1 Answers1