How to check if a binary tree is symmetric (recursive 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)
    {
    }
}

We already saw how to solve this problem. Previously we were using the iterative approach. Now let's take a look at how it can be solved with a recursive approach.

Approach:

A tree is symmetric if the root's children are symmetric and children of children are symmetric. The algorithm could look like

• check if two nodes (left and right) are symmetric
• check if children from left and right nodes are symmetric as well

 

Code

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

        return IsSymmetric(root.Left, root.Right);
    }

    private bool IsSymmetric(TreeNode left, TreeNode right)
    {
        if (left == null && right == null)
        {
            return true;
        }

        if (left == null || right == null)
        {
            return false;
        }

        if (left.Value == right.Value)
        {
            return IsSymmetric(left.Left, right.Right) && IsSymmetric(left.Right, right.Left);
        }

        return false;
    }