🚀 Leaf-Similar Trees | DFS Recursive & Iterative Solution | Binary Tree | #Leetcode75 #Python #DFS

🌳 Leaf-Similar Trees (Leetcode 75 - Binary Tree)

In this problem, we need to determine if two binary trees have the same leaf sequence when traversed from left to right.

📌 What is a Leaf-Similar Tree?

A leaf node is a node that has no left or right children.
The leaf sequence of a binary tree is the order of leaf nodes when traversed left to right.
Two trees are leaf-similar if their leaf sequences are the same.

🔹 Approach

1️⃣ Extract Leaf Sequence

We traverse the tree using DFS (Depth-First Search).
Whenever we find a leaf node, we add its value to a list.
We do this for both trees.

2️⃣ Compare the Two Lists

If both lists are identical, return True.
Otherwise, return False.

✅ Python Solution Using DFS (Recursive)

class TreeNode:
def __init__(self, val=0, left=None, right=None):
self.val = val
self.left = left
self.right = right

class Solution:
def getLeafSequence(self, root, leaves):
if not root:
return
if not root.left and not root.right: # If it's a leaf node
leaves.append(root.val)
self.getLeafSequence(root.left, leaves)
self.getLeafSequence(root.right, leaves)

def leafSimilar(self, root1, root2):
leaves1, leaves2 = [], []
self.getLeafSequence(root1, leaves1)
self.getLeafSequence(root2, leaves2)
return leaves1 == leaves2

🔹 Explanation:

We define getLeafSequence(root, leaves), which stores the leaf nodes in a list.
We call this function for both trees and compare the results.
If the two lists are identical, return True; otherwise, return False.

✅ Python Solution Using DFS (Iterative)

class Solution:
def getLeafSequence(self, root):
stack, leaves = [root], []

while stack:
node = stack.pop()
if node:
if not node.left and not node.right: # If it's a leaf node
leaves.append(node.val)
stack.append(node.right) # Process right first (LIFO)
stack.append(node.left) # Then process left

return leaves

def leafSimilar(self, root1, root2):
return self.getLeafSequence(root1) == self.getLeafSequence(root2)

🔹 Explanation:

Instead of recursion, we use a stack for iterative DFS traversal.
We collect leaf values and return the final list.
If the leaf sequences of both trees match, return True.

🔹 Complexity Analysis

Approach Time Complexity Space Complexity Method
DFS (Recursive) O(N1 + N2) O(H1 + H2) Recursive function calls
DFS (Iterative) O(N1 + N2) O(H1 + H2) Stack-based traversal

✅ Best for Practice: This problem tests your DFS skills and tree traversal techniques!

💬 Which approach do you prefer? Drop a comment below! 👇

#Leetcode #BinaryTree #DFS #CodingInterview #Python #Leetcode75 #Algorithms #Recursion #Iterative #TreeTraversal

Видео 🚀 Leaf-Similar Trees | DFS Recursive & Iterative Solution | Binary Tree | #Leetcode75 #Python #DFS канала CodeVisium