LeetCode — 101. Symmetric Tree

Iteration Version

Symmetry in binary trees is a concept where a tree is a mirror image of itself around its center. This property is not only aesthetically pleasing but also carries significance in various computational scenarios. In this post, we’ll explore an iterative method using queues to determine whether a binary tree is symmetric, offering an alternative to the recursive approach.

The Queue-Based Iterative

Approach While recursion is a natural fit for many tree-related algorithms, the iterative approach can be more intuitive for certain problems and avoids the potential stack overflow issues with recursion. For checking tree symmetry, an iterative method with a queue can be particularly efficient.

Implementation Strategy

The function isSymmetric starts by checking if the root is null. A null root inherently means the tree is symmetric. If the root is not null, we proceed with the following steps:

1. Queue Initialization: We initialize a queue and enqueue the left and right children of the root node. The queue will help us pair nodes from each level to compare their symmetry.
2. Symmetry Check Loop: The loop runs as long as there are nodes in the queue. In each iteration, we dequeue two nodes for comparison.
3. Node Comparison:

• Null Check: If both dequeued nodes are null, we continue to the next iteration, as a pair of nulls is symmetric.
• Symmetry Validation: If one node is null and the other isn’t, or if the values of the nodes don’t match, the tree isn’t symmetric, and we return false.

4. Enqueue Child Nodes: For nodes that pass the symmetry check, we enqueue their children in a cross-pattern: the left child of the left node with the right child of the right node, and the right child of the left node with the left child of the right node.

Why an Iterative Queue Approach?

• Level-by-Level Processing: The queue naturally facilitates a breadth-first traversal, allowing us to process nodes level by level and compare corresponding pairs efficiently.
• Explicit Pairing: By enqueuing nodes in pairs, we maintain the necessary structure to validate symmetry at each level.
• Non-Recursive: This method is iterative and doesn’t rely on the call stack, making it suitable for large trees where recursive depth might be a concern.

Complexity Analysis

• Time Complexity: O(n), where n is the number of nodes in the binary tree. Each node is visited once.
• Space Complexity: O(n), as the queue can hold all nodes at the largest breadth level in the worst case.

JavaScript version

/**
 * Definition for a binary tree node.
 * function TreeNode(val, left, right) {
 *     this.val = (val===undefined ? 0 : val)
 *     this.left = (left===undefined ? null : left)
 *     this.right = (right===undefined ? null : right)
 * }
 */
/**
 * @param {TreeNode} root
 * @return {boolean}
 */
// iteration - queue
var isSymmetric = function (root) {
    if (root === null) return null;

    const queue = [];
    queue.push(root.left);
    queue.push(root.right);

    let leftNode = null, rightNode = null;
    while (queue.length !== 0) {
        leftNode = queue.shift();
        rightNode = queue.shift();

        // if left and right node are null, it is symmetric
        if (leftNode === null && rightNode === null) {
            continue;
        }

        if ((leftNode === null && rightNode !== null) ||
            (leftNode !== null && rightNode === null) ||
            (leftNode.val !== rightNode.val)) {
            return false;
        }

        queue.push(leftNode.left);
        queue.push(rightNode.right);
        queue.push(leftNode.right);
        queue.push(rightNode.left);
    }

    return true;
}