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

Given two binary trees that are duplicates of one another, and given a node in one tree, find that correponding node in the second tree.

For instance, in the tree below, we’re looking for Node #4.

For this problem, you can assume that:

• There can be duplicate values in the tree (so comparing node1.value == node2.value isn’t going to work).

Can you solve this both recursively and iteratively?

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

def findNode(a, b, node):
  # Fill this in.

#  1
# / \
#2   3
#   / \
#  4*  5
a = Node(1)
a.left = Node(2)
a.right = Node(3)
a.right.left = Node(4)
a.right.right = Node(5)

b = Node(1)
b.left = Node(2)
b.right = Node(3)
b.right.left = Node(4)
b.right.right = Node(5)

print(findNode(a, b, a.right.left))
# 4