Symmetric Tree

// C++
class Solution {
public:
    bool checkSymmetry(TreeNode* rootNode) {
        queue<TreeNode*> nodesQueue;
        nodesQueue.push(rootNode);
        nodesQueue.push(rootNode);
        while (!nodesQueue.empty()) {
            TreeNode* nodeLeft = nodesQueue.front();
            nodesQueue.pop();
            TreeNode* nodeRight = nodesQueue.front();
            nodesQueue.pop();
            if (nodeLeft == NULL && nodeRight == NULL) continue;
            if (nodeLeft == NULL || nodeRight == NULL) return false;
            if (nodeLeft->val != nodeRight->val) return false;
            nodesQueue.push(nodeLeft->left);
            nodesQueue.push(nodeRight->right);
            nodesQueue.push(nodeLeft->right);
            nodesQueue.push(nodeRight->left);
        }
        return true;
    }
};

To determine if a binary tree is symmetric around its center, the provided solution in C++ uses an iterative approach utilizing a queue data structure. The function checkSymmetry() takes a single parameter, rootNode, which represents the root of the binary tree.

• Begin by defining a queue data structure to hold nodes from the tree.

• Add rootNode to the queue twice. This step initiates the process to check symmetry by comparing each node to its mirror counterpart across the tree's center.

• Use a loop to iterate as long as the queue contains elements. Inside the loop:

  • Remove two nodes from the front of the queue and assign them to two variables—nodeLeft and nodeRight. These represent the nodes that need to be symmetric.

  • Perform null checks on both nodes. If both are null, proceed without adding more nodes to the queue since null nodes at the same position in both subtrees still preserve symmetry. If only one of the nodes is null, symmetry is broken, and return false.

  • Compare the values of nodeLeft and nodeRight. If they are unequal, the tree is not symmetric; return false.

  • To continue checking for symmetry deeper in the tree, add the left and right children of nodeLeft and the right and left children of nodeRight to the queue, respectively. This step cross-checks the nodes from opposite sides of the tree.

• After the loop, if no asymmetry is found, return true, indicating that the tree is symmetric.

This approach ensures that each level of the tree is checked for symmetry efficiently without recursion, which can be more intuitive and easier to understand for maintaining tree structure relations complexity. The iterative method also helps in managing larger trees by maintaining a clear order of checks and balances via explicit queue management.

class Solution {
    public boolean isTreeSymmetric(TreeNode rootNode) {
        Queue<TreeNode> nodesQueue = new LinkedList<>();
        nodesQueue.add(rootNode);
        nodesQueue.add(rootNode);
        while (!nodesQueue.isEmpty()) {
            TreeNode leftNode = nodesQueue.poll();
            TreeNode rightNode = nodesQueue.poll();
            if (leftNode == null && rightNode == null) continue;
            if (leftNode == null || rightNode == null) return false;
            if (leftNode.val != rightNode.val) return false;
            nodesQueue.add(leftNode.left);
            nodesQueue.add(rightNode.right);
            nodesQueue.add(leftNode.right);
            nodesQueue.add(rightNode.left);
        }
        return true;
    }
}

The provided Java code defines a method to determine whether a binary tree is symmetric around its center. Symmetry in a binary tree means the left subtree is a mirror reflection of the right subtree.

• The method isTreeSymmetric checks if a given binary tree is symmetric.

• It employs a Queue<TreeNode> to keep track of nodes to be compared.

• The queue initially contains the root node twice.

• The method uses a while loop to process nodes in the queue until it's empty.

  • It dequeues two nodes at a time representing the left and right sides.
  • Continues without action if both nodes are null (mirroring empty subtrees).
  • Returns false if only one of the compared nodes is null, as this breaks symmetry.
  • Also returns false if the values of the nodes do not match.

• If the nodes match, the method enqueues their children in a specific order to compare left with right and vice versa in subsequent iterations.

• If all comparisons hold, the method concludes the tree is symmetric and returns true.

This implementation effectively uses breadth-first search to ensure each level of the tree is symmetric, considering all edge cases such as the presence of single children and varying node values.

// C
bool checkSymmetry(struct TreeNode* root) {
    struct TreeNode* queue[3030];
    int start = 0;
    int end = 0;
    queue[start++] = root;
    queue[start++] = root;
    while (start != end) {
        struct TreeNode* leftNode = queue[end++];
        struct TreeNode* rightNode = queue[end++];
        if (leftNode == NULL && rightNode == NULL) continue;
        if (leftNode == NULL || rightNode == NULL) return false;
        if (leftNode->val != rightNode->val) return false;
        queue[start++] = leftNode->left;
        queue[start++] = rightNode->right;
        queue[start++] = leftNode->right;
        queue[start++] = rightNode->left;
    }
    return true;
}

The provided C code defines a function checkSymmetry that determines whether a binary tree is symmetric around its center. The function utilizes a breadth-first search approach with the help of a queue data structure.

• The function starts by initializing a queue to help with the node traversal.
• Both the root node is enqueued twice as the algorithm compares nodes in pairs - one from the left subtree and the other from the right subtree.

The core of the function operates within a while loop that continues as long as there are elements in the queue.

• In each iteration, two nodes are dequeued concurrently and their symmetry is checked.
• If both nodes are NULL, the comparison proceeds without returning false, as NULL nodes on both sides are symmetric.
• If one node is NULL and the other is not, the tree cannot be symmetric, hence the function returns false.
• Then, if the values of both nodes aren't equal, it indicates asymmetry and thus, false is returned.
• For continued verification of symmetry deeper in the tree, the function enqueues the left child of the first node and the right child of the second node. It then enqueues the right child of the first node and the left child of the second node, hence maintaining the pattern required for symmetry verification.
• Once the loop completes without finding any asymmetrical conditions, the function will return true.

This approach ensures that each level of the tree is mirrored against its opposite side, thereby effectively checking for symmetrical structure throughout the tree.

var checkMirrorTrees = function (node) {
    let queue = [node, node];
    while (queue.length > 0) {
        let first = queue.shift();
        let second = queue.shift();
        if (first === null && second === null) {
            continue;
        }
        if (first === null || second === null) {
            return false;
        }
        if (first.val !== second.val) {
            return false;
        }
        queue.push(first.left, second.right, first.right, second.left);
    }
    return true;
};

The provided JavaScript function, checkMirrorTrees, determines if a tree is symmetric around its center, a common problem in binary tree data structures. This function utilizes a breadth-first search approach with a queue. Here's how it works:

1. Initialize a queue with the root node passed in twice. This allows comparison of two nodes at a time, simulating a mirror image check.
2. Use a while loop to process nodes until the queue is empty. Within each iteration, two nodes are dequegged:
   • Check if both nodes are null. If true, move to the next iteration without doing anything. This scenario arises when checking symmetric subtrees both ending in leaf nodes.
   • If one of the nodes is null but not the other, return false, as this indicates asymmetry.
   • Compare the values of the two nodes. If they don't match, return false.
3. Push the children of the nodes into the queue in a crosswise manner: first's left with second's right and first's right with second's left. This cross-matching ensures that each level of the tree is checked for mirror symmetry.

If the function exits the loop without encountering asymmetry, it returns true, confirming that the tree is symmetric.

class Solution:
    def checkSymmetry(self, rootNode):
        elements = [rootNode, rootNode]
        while elements:
            node1 = elements.pop(0)
            node2 = elements.pop(0)
            if node1 is None and node2 is None:
                continue
            if node1 is None or node2 is None:
                return False
            if node1.val != node2.val:
                return False
            elements.append(node1.left)
            elements.append(node2.right)
            elements.append(node1.right)
            elements.append(node2.left)
        return True

The provided code defines a Python function checkSymmetry within a class named Solution. This function is used to determine if a binary tree is symmetric around its center. Symmetry in this context means the tree appears the same when observed from the left or right.

To achieve this, the solution employs an iterative approach using a list named elements to simulate a queue for breadth-first traversal:

• Initially, the queue is populated with the root node twice.
• The function enters a loop, processing two nodes at a time (regarded as mirror counterparts in the symmetry check).
• The loop continues until the queue is empty:
  • Two nodes are popped from the front of the queue.
  • The function checks if both nodes are None, in which case the loop simply continues.
  • If only one of the nodes is None, the function returns False as it implies asymmetry at this level of the tree.
  • If the values of the two nodes differ, False is returned because the nodes do not mirror each other.
  • If the two nodes pass the above checks, their children are added to the queue in an order that compares left with right children across the two nodes.
• If all mirrored node pairs pass the checks throughout the traversal, the function returns True, confirming the tree's symmetry.

This implementation provides a clear and efficient method to check for symmetry in a binary tree, leveraging the properties of breadth-first search and queue data structure.