DEV Community

Urfan Guliyev
Urfan Guliyev

Posted on

Leetcode - Symmetric Tree (with JavaScript)

Today I am going to show how to solve the Symmetric Tree algorithm problem.

Here is the problem:
Alt Text

In this problem we need to test whether or not a binary tree is symmetrical in its structure and value. The question then is: when are two trees a mirror reflection of each other?

A tree is symmetric if the left subtree is a mirror reflection of the right subtree. If we draw a line down the middle of our tree, the tree can fold on itself and its node values will be equivalent.

Now, I am going to solve it recursively.

1) First, I check the root node. If it is null, no further action is needed. If it is not null, we need to go into recursion and check both the left and right subtrees.

var isSymmetric = function(root) {
    if (root == null) return true;
    return isMirror(root.left, root.right);
};
Enter fullscreen mode Exit fullscreen mode

2) If a left subtree and a right subtree are both null, it means that they are symmetric. If just one of them is null, then they are asymmetric.

var isSymmetric = function(root) {
    if (root == null) return true;
    return isMirror(root.left, root.right);
};

const isMirror = function(leftSub, rightSub) {
    if (leftSub == null && rightSub == null) return true;
    if (leftSub == null || rightSub == null) return false;
}
Enter fullscreen mode Exit fullscreen mode

3) If they are both not null, we need to check their values. If they are the same, we are going to continue our recursion to the left and to the right of the nodes. We have to make sure that our left subtree’s left node is equivalent to our right subtree’s right node, and our left subtree’s right node is equivalent to our right subtree’s left node.

var isSymmetric = function(root) {
    if (root == null) return true;
    return isMirror(root.left, root.right);
};

const isMirror = function(leftSub, rightSub) {
    if (leftSub == null && rightSub == null) return true;
    if (leftSub == null || rightSub == null) return false;

    return (leftSub.val === rightSub.val 
            && isMirror(leftSub.left, rightSub.right) 
            && isMirror(leftSub.right, rightSub.left))
}
Enter fullscreen mode Exit fullscreen mode

Top comments (0)