Pseudo-Palindromic Paths in a Binary Tree

Given a binary tree where node values are digits from 1 to 9. A path in the binary tree is said to be pseudo-palindromic if at least one permutation of the node values in the path is a palindrome.

Return the number of pseudo-palindromic paths going from the root node to leaf nodes.

Example:

Input: root = [2,3,1,3,1,null,1]
Output: 2 

Approach:

C++

#include <bits/stdc++.h>
using namespace std;
//struct for treenode
struct TreeNode
{
    int data;
    TreeNode *left;
    TreeNode *right;
    TreeNode(int data)
    {
        this->data = data;
        this->left = NULL;
        this->right = NULL;
    }
};
int countVal = 0;

void dfs(TreeNode *root, int path)
{

    //if root is NULL then
    //return
    //base case to terminate the recursion
    if (root == NULL)
        return;
    path = path ^ (1 << root->data);

    //if leaf node
    if (root->left == NULL && root->right == NULL)
    {

        countVal += (path & (path - 1)) == 0 ? 1 : 0;
        return;
    }

    //call for left subtree
    dfs(root->left, path);

    //call for right subtree
    dfs(root->right, path);
}
int pseudoPalindromicPaths(TreeNode *root)
{
    dfs(root, 0);
    return countVal;
}

int main()
{
    TreeNode *root = new TreeNode(2);
    root->left = new TreeNode(3);
    root->right = new TreeNode(1);
    root->left->left = new TreeNode(3);
    root->left->right = new TreeNode(1);
    root->right->right = new TreeNode(1);

    cout << pseudoPalindromicPaths(root);

    return 0;
}