Mirror Tree

#Amazon #Medium #Tree

Question

Given a root node, check whether the given tree is a mirror tree or not.

Explanation Video

Explain how to approach the question and coding explanation as well.

Solution

Use queues to collect nodes to compare in the right order and compare them all at the same time.

  class Node {
    int value;
    List<Node> children;
  }
  
  private Queue<Node> constructQueue(Node node, boolean isLeft) {
    // This queue contains all children sorted in specific orders:
    // - Left-node: inserted by right-left and level by level.
    // - Right-node: inserted by left-right and level by level.
    Queue<Node> queue = new LinkedList<>();

    // This queue will be used to iterate thorough the entire
    // children of the given node.
    Queue<Node> iteratingQueue = new LinkedList<>();
    iteratingQueue.add(node);

    // Iteratively go through all children level by level
    // either "left to right" or "right to left."
    while (!iteratingQueue.isEmpty()) {
      Node currentNode = iteratingQueue.poll();
      queue.add(currentNode);

      // If the given node is a left node, put
      // children nodes in the iterator queue w/ a reverse order.
      List<Node> children = (isLeft) ?
              Lists.reverse(currentNode.children) :
              currentNode.children;
      iteratingQueue.addAll(children);
    }

    return queue;
  }

  // Check whether the given left node is the
  // mirrored image of the given right node.
  private boolean isMirror(Node left, Node right) {
    Queue<Node> leftQueue = constructQueue(left, true);
    Queue<Node> rightQueue = constructQueue(right, false);

    // Compare the children of given left and right node and return if we
    // find any children that does not have the mirrored image.
    while (!leftQueue.isEmpty() && !rightQueue.isEmpty()) {
      Node leftNode = leftQueue.poll();
      Node rightNode = rightQueue.poll();
      if (leftNode.value != rightNode.value
          || leftNode.children.size() != rightNode.children.size()) {
        return false;
      }
    }

    // Make sure that both queues are empty when the comparision is complete.
    return leftQueue.isEmpty() && rightQueue.isEmpty();
  }

  private boolean isTreeMirror(Node root) {
    List<Node> children = root.children;

    int left = 0;
    int right = children.size() - 1;
    while (left < right) {
      if (!isMirror(children.get(left), children.get(right))) {
        return false;
      }

      left ++;
      right --;
    }

    // If the left & right indexes are the same after the while loop above,
    // it means the number of root's children is odd. If that's the case, you
    // need to make sure the middle children contains the mirror image as well.
    if (left == right) {
      Node middleNode = children.get(left);
      return isTreeMirror(middleNode);
    }

    return true;
  }