# C++ 3ms using map

• Maps probably use more space than queues but it performed faster somehow than my queue solution.

``````class Solution {
public:
bool isSymmetric(TreeNode* root) {
if (!root) return true;
// put left side in a map // <position, number>
unordered_map<int, int> mapleft, mapright;
mapNodes(root->left, mapleft, 1),
mapNodes(root->right, mapright, 2);

// iterating through left side, check right side, symmetric at the same left
for (auto itr = mapleft.begin(); itr != mapleft.end(); itr++) {
// look for the symmetric node. if found, erase it
int pos = itr->first;
int d = log2(pos + 1);

int start = pow(2, d) - 1;
int end = 2 * start;

int sympos = end - pos + start;

// now check if sympos exists in mapright and has the same value. if so, erase it
auto symitr = mapright.find(sympos);
if (symitr == mapright.end())			// if symmetric position has no node
return false;
else
if (itr->second == symitr->second)	// if symmetric node has a different val, erase it
mapright.erase(symitr);
else
return false;

}
// mapright should be empty, after mapleft traversal removed all symmetric nodes
if (mapright.empty())
return true;

return false;
}

void mapNodes(TreeNode *p, unordered_map<int, int> &ht, int pos) {
if (!p) return;

// preorder traversal
ht[pos] = p->val;

mapNodes(p->left, ht, pos * 2 + 1);
mapNodes(p->right, ht, pos * 2 + 2);
}
};
``````

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.