#60 Finding Equivalent Subtrees by Letter Set

Companies:

Yandex

Themes:

AlgorithmsTreesPractice

A rooted binary tree is given, and each vertex contains one letter from A-Z. Two vertices are considered equivalent if the subtrees rooted at those vertices contain the same set of letters, without considering frequencies. Find any pair of equivalent vertices:

/*
             A
           /   \
          C     B
         / \   / \
        A   D A   D
       /           \
      B             C
*/
class TNode {
    char value = '\0'; // [A-Z]
    TNode left = null;
    TNode right = null;
};

Pair<TNode, TNode> findEquivalentSubtrees(TNode root) {
    ...
}

Question review

Mentor

Answer as you would in a real interview. I’ll ask follow-up questions, then compare your answer with the reference answer and show your accuracy as a %.

Sign in to start the dialogue The mentor keeps the context of the current question and your previous messages.