Same Binary Tree - Leetcode 100 - Trees (Python)

[@GregHogg]

Master Data Structures & Algorithms For FREE at AlgoMap.io!

[@wallwall3140]

u deserve a medal 🥇 thanks a lot

[@shreyageek]

this also works for all test cases without defining additional function var isSameTree = function(p, q) { if(!p && !q) return true; if(p&& !q || q &&!p) return false; if(p.val != q.val) return false; return (isSameTree(p.left,q.left) && isSameTree(p.right , q.right) ) };

[@theomichel8405]

Can someone explain why not use bfs in this case ?

[@boiledtoenail]

Someone correct me if im wrong but recursive calls make it dfs in general due to it being a call stack (FIFO) and all that.

[@Infinitely16]

You could do a BFS solution. The point is the visit all nodes in both trees at the same time. Both BFS and DFS accomplish this. DFS is just a preference.

[@rollbacked]

damn my solution was not that smart, I did a dfs helper function (doing it explicitly w/ a stack) that returned a visited array and did a comparison function dfs(p) == dfs(q) to check if the two trees were the same class Solution: def isSameTree(self, p: Optional[TreeNode], q: Optional[TreeNode]) -> bool: def dfs(node): stack = [node] visited = [] while stack: curr_node = stack.pop() if curr_node: visited.append(curr_node.val) stack.append(curr_node.left) stack.append(curr_node.right) if curr_node is None: visited.append('null') # trees are equal if they have the same null values too return visited return dfs(p) == dfs(q)