Hi, here’s your problem today. This problem was recently asked by Microsoft:

Given a tree, the leaves form a certain order from left to right. Two trees are considered “leaf-similar” if their leaf orderings are the same.

For instance, the following two trees are considered leaf-similar because their leaves are [2, 1]:
3
/ \
5 1

2
7
/ \
2 1

2
Our job is to determine, given two trees, whether they are “leaf similar.”

class Node(object):
def **init**(self, x):
self.val = x
self.left = None
self.right = None

class Solution(object): def leafSimilar(self, root1, root2): # Fill this in.

# 3

# / \

# 5 1

# \

# 2

t1 = Node(3) t1.left = Node(5) t1.right = Node(1) t1.left.left = Node(6) t1.left.right = Node(2)

# 7

# / \

# 2 1

# \

# 2

t2 = Node(7) t2.left = Node(2) t2.right = Node(1) t2.left.left = Node(6) t2.left.right = Node(2)

print(Solution().leafSimilar(t1, t2))