Teaching Kids Programming – Recursive Depth First Search Algorithm to Compare Leaf Equivalent Trees

Teaching Kids Programming: Videos on Data Structures and Algorithms

Given two binary trees root0 and root1, return whether the sequence of leaves left-to-right in both trees are the same.

Constraints
n ≤ 100,000 where n is the number of nodes in root0
m ≤ 100,000 where m is the number of nodes in root1

Compare Leaf Equivalent Trees by Using Recursive Depth First Search Algorithm

We can perform a DFS (Depth First Search) Algorithm and return the leaf nodes by the order (similar to Pre-Order). Then, we can just compare the order by two given trees to see if they have same/equivalent leaves.

# class Tree:
#     def __init__(self, val, left=None, right=None):
#         self.val = val
#         self.left = left
#         self.right = right
class Solution:
    def checkLeafEquivalent(self, root0, root1):
        def dfs(root):
            if root is None:
                return []
            if root.left is None and root.right is None:
                return [root.val]
            return dfs(root.left) + dfs(root.right)
        return dfs(root0) == dfs(root1)

Time complexity is O(N+M) where N and M are the number of the nodes in two given binary trees respectively. The space complexity is also O(N+M). The DFS is implemented using Recursion.

–EOF (The Ultimate Computing & Technology Blog) —