LC 101 Symmetric tree

Given a binary tree, check whether it is a mirror of itself (ie, symmetric around its center).

For example, this binary tree [1,2,2,3,4,4,3] is symmetric:

But the following [1,2,2,null,3,null,3] is not:

Note: Bonus points if you could solve it both recursively and iteratively.

Recursive

A tree is symmetric if the two subtrees beneath any root has:

  1. the left and right child has the same value
  2. The left child’s left matches with right child’s right
  3. The left child’s right matches with left child’s left.

The base case is when two leaf level node matches and they don’t have children.

    bool isSymmetric(TreeNode* root) {
        return isSym(root, root);
    }
    bool isSym(TreeNode* leftNode, TreeNode* rightNode){
        if(leftNode == NULL && rightNode != NULL) return false;
        if (leftNode != NULL && rightNode == NULL)return false;
        if(leftNode == NULL && rightNode == NULL) return true;
        return (leftNode -> val == rightNode -> val &&
            isSym(leftNode -> left, rightNode -> right) && 
            isSym(leftNode -> right , rightNode -> left));
    }

Improvement

In the previous code, we have three coditions to check, but observe that it only wants to know if both nodes are null or just one is null so we can do

if(leftNode == NULL && rightNode == NULL) return true;
if(left == NULL || right == NULL) return falase;

ITerative

    bool isSymmetric(TreeNode* root) {
        stack<TreeNode*> s;
        s.push(root);
        s.push(root);
        while(!s.empty()){
            TreeNode* leftNode = s.top();
            s.pop();
            TreeNode* rightNode = s.top();
            s.pop();
            if(leftNode == NULL && rightNode == NULL) continue;
            if(leftNode == NULL || rightNode == NULL) return false;
            if(leftNode -> val == rightNode -> val){
                s.push(leftNode -> left);
                s.push(rightNode -> right);
                s.push(leftNode -> right);
                s.push(rightNode -> left);
            }
            else
                return false;
        }
        return true;
    }

Leave a Reply

Your email address will not be published. Required fields are marked *

To create code blocks or other preformatted text, indent by four spaces:

    This will be displayed in a monospaced font. The first four 
    spaces will be stripped off, but all other whitespace
    will be preserved.
    
    Markdown is turned off in code blocks:
     [This is not a link](http://example.com)

To create not a block, but an inline code span, use backticks:

Here is some inline `code`.

For more help see http://daringfireball.net/projects/markdown/syntax