Skip to interview prep
Apexed

167. When are two binary trees isomorphic, and when are they quasi-isomorphic?

MediumTrees

Technical
Show model answer

Two trees are isomorphic when they have the same shape, ignoring values: both empty, or both non-empty with isomorphic left subtrees and isomorphic right subtrees. That check is O(min(n, m)) time.

Quasi-isomorphic trees can be made identical in shape by swapping the children of some nodes. The recursive test accepts if (left~left and right~right) or (left~right and right~left). With short-circuiting this is often fast, but the four recursive calls per node can make it quadratic on balanced trees. To guarantee near-linear time, compute a canonical code for each subtree bottom-up (order the two child codes before combining) and compare the root codes.

When are two binary trees isomorphic, and when are they quasi-isomorphic — Data structures & algorithms interview question — Apexed