How to check if a binary tree is symmetric (iterative approach)

A binary tree is a hierarchical data structure. A binary tree consists of nodes, each node has:

• A left node
• A right node
• A data element, which could be of any type

Given a binary tree. Write a method to check does the tree symmetric around the center or not

Example

 

Output: True

 

/* Definition for TreeNode
public class TreeNode
{
    public int Value;
    public TreeNode Left;
    public TreeNode Right;

    public TreeNode(int value)
    {
        Value = value;
    }
}
*/

public sealed class Solution
{
    public bool IsSymmetric(TreeNode root)
    {
    }
}

Algorithm

Let's ponder, what does it mean symmetric around the center. We can imagine a line goes threw the root node and all nodes will be symmetric around this line. A tree is symmetric if a left subtree is symmetric to a right subtree, other words:

• if left subtree has node than a right subtree should have a symmetric node with the same value
• if left subtree doesn't have node than a right subtree should not have node too.

In this case, a given example should look like:

 

 

This approach can be easily implemented through breadth-first search.

 

Code

public bool IsSymmetric(TreeNode root)
{
    if (root == null)
    {
        return true;
    }

    var queue = new Queue<TreeNode>();
    queue.Enqueue(root.Left);
    queue.Enqueue(root.Right);

    while (queue.Count != 0)
    {
        TreeNode one = queue.Dequeue();
        TreeNode two = queue.Dequeue();

        if (one == null && two == null)
        {
            continue;
        }

        if (one == null || two == null)
        {
            return false;
        }

        if (one.Value != two.Value)
        {
            return false;
        }

        queue.Enqueue(one.Left);
        queue.Enqueue(two.Right);

        queue.Enqueue(one.Right);
        queue.Enqueue(two.Left);
    }

    return true;
}