Teaching Kids Programming – Leaf Similar Trees by Recursive Depth First Search Algorithm

Teaching Kids Programming: Videos on Data Structures and Algorithms

Consider all the leaves of a binary tree, from left to right order, the values of those leaves form a leaf value sequence. For example, in the given tree above, the leaf value sequence is (6, 7, 4, 9, 8). Two binary trees are considered leaf-similar if their leaf value sequence is the same. Return true if and only if the two given trees with head nodes root1 and root2 are leaf-similar.

Example 1:
Input: root1 = [3,5,1,6,2,9,8,null,null,7,4], root2 = [3,5,1,6,7,4,2,null,null,null,null,null,null,9,8]
Output: true

Example 2:
Input: root1 = [1], root2 = [1]
Output: true

Example 3:
Input: root1 = [1], root2 = [2]
Output: false

Example 4:
Input: root1 = [1,2], root2 = [2,2]
Output: true

Example 5:
Input: root1 = [1,2,3], root2 = [1,3,2]
Output: false

Constraints:
The number of nodes in each tree will be in the range [1, 200].
Both of the given trees will have values in the range [0, 200].

Recursive Depth First Search Algorithm to Check Leaf Similar Trees

We perform Depth First Search to get the sequence of the leafs in the preorder. We can implement a DFS function to return a list of leaves for the current binary tree in the preorder (from left to the right), and then compare the leaves lists for two binary trees.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22

# 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 leafSimilar(self, root1: TreeNode, root2: TreeNode) -> bool:
        def dfs(node):
            if not node:
                return
            ans = []
            if not node.left and not node.right:
                ans.append(node.val)
            left = dfs(node.left)
            if left:
                ans += left
            right = dfs(node.right)
            if right:
                ans += right
            return ans
        return dfs(root1) == dfs(root2)

# 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 leafSimilar(self, root1: TreeNode, root2: TreeNode) -> bool:
        def dfs(node):
            if not node:
                return
            ans = []
            if not node.left and not node.right:
                ans.append(node.val)
            left = dfs(node.left)
            if left:
                ans += left
            right = dfs(node.right)
            if right:
                ans += right
            return ans
        return dfs(root1) == dfs(root2)

We can use the yield and yield from instead of returning a list – which gives simpler/shorter implementation:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16

# 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 leafSimilar(self, root1: TreeNode, root2: TreeNode) -> bool:
        def dfs(node):
            if not node:
                return
            if not node.left and not node.right:
                yield node.val
            yield from dfs(node.left)
            yield from dfs(node.right)
        return list(dfs(root1)) == list(dfs(root2))

# 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 leafSimilar(self, root1: TreeNode, root2: TreeNode) -> bool:
        def dfs(node):
            if not node:
                return
            if not node.left and not node.right:
                yield node.val
            yield from dfs(node.left)
            yield from dfs(node.right)
        return list(dfs(root1)) == list(dfs(root2))

Then, we need to convert the generator to list – comparing the generator directly will always give a false result.

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

–EOF (The Ultimate Computing & Technology Blog) —