Compare Trees Early Exit | Dataford Interview Questions

Beckman Coulter Diagnostics software can represent analyzer configuration data as binary trees. Given two such trees, determine whether they are identical, and stop traversing immediately when a difference is found.

Two trees are identical when corresponding nodes have the same integer value and the same structure. A missing child is represented by None.

Formal Specification

Implement compare_trees(tree1, tree2). Each tree is either None or a dictionary with exactly three fields: value, left, and right. The left and right fields contain another tree or None. Return a boolean: True if the trees are identical, otherwise False.

Your implementation must short-circuit. Once a corresponding pair of nodes differs in value or structure, it must return without visiting any remaining subtrees.

Constraints

Each tree contains between 0 and 10^5 nodes.
Node values are integers from -10^9 through 10^9.
Tree height can be as large as the number of nodes.
Every non-empty node has the fields value, left, and right.

Function Signature

def compare_trees(tree1, tree2):

Your question is Compare Trees Early Exit. Start with the requirements in the Question tab.

Run and submit as often as you like. When you're ready, talk me through your approach or go straight to the code.

Problem