🌱 Keegan's Digital Garden

1457. Pseudo-Palindromic Paths in a Binary Tree

3 min read

📝 Problem Details

🔭 Key Observations

1. A palindrome requires all characters to have an even frequency, except for at most one character.
   - A pseudo-palindromic path allows at most one digit to have an odd frequency.

2. The task is to traverse all root-to-leaf paths and count how many of them are pseudo-palindromic.

3. Use a frequency array `freq` of size 10 (digits 1-9) to keep track of the count of digits along the current path.

4. Backtracking is used to restore the state of `freq` after traversing each subtree.

5. A helper function `isPseudoPalindromic` checks whether the `freq` array satisfies the pseudo-palindromic condition:
   - Count how many digits have an odd frequency.
   - If the odd count is greater than 1, the path is not pseudo-palindromic.

💡 Explanation of Solution

### General Algorithm

1. **Initialize Frequency Array**:
    
    - Use a vector `freq` of size 10 to keep track of digit frequencies along the current path.
2. **DFS Traversal**:
    
    - Traverse the tree using a depth-first search (DFS).
    - At each node:
        - Increment the frequency of the node's value in `freq`.
        - If it’s a leaf node, check if the path is pseudo-palindromic using the `isPseudoPalindromic` function.
        - Recur for the left and right children.
        - Backtrack by decrementing the frequency of the current node's value before returning.
3. **Check Palindromic Condition**:
    
    - A helper function `isPseudoPalindromic` checks the `freq` array for the pseudo-palindromic condition:
        - Count how many digits have an odd frequency.
        - If more than one digit has an odd frequency, the path is not pseudo-palindromic.
4. **Return Result**:
    
    - The total count of pseudo-palindromic paths is returned after the DFS completes.

### Steps

1. Start at the root of the tree.
2. Traverse the tree recursively using DFS, updating the frequency array at each node.
3. At each leaf node, check if the current path is pseudo-palindromic.
4. Backtrack after processing each node to ensure the frequency array reflects the correct state for the parent node.
5. Return the total count of valid paths.

⌛ Complexity Analysis

1. **Time Complexity**:
   - Each node is visited exactly once during the DFS traversal.
   - At each node, checking the pseudo-palindromic condition involves iterating over the `freq` array of size 10.
   - Total time complexity: `O(n)`, where `n` is the number of nodes in the tree.

2. **Space Complexity**:
   - The `freq` array uses `O(10)` space.
   - The recursion stack depth is proportional to the height of the tree:
     - For a balanced tree: `O(log n)`
     - For a skewed tree: `O(n)`
   - Overall space complexity: `O(h)`, where `h` is the height of the tree.

💻 Implementation of Solution

class Solution {
public:
    int pseudoPalindromicPaths(TreeNode* root) {
        vector<int> freq(10, 0); // Frequency array for digits 1-9
        return dfs(root, freq);
    }
 
private:
    int dfs(TreeNode* node, vector<int>& freq) {
        if (!node) return 0;
 
        // Increment the frequency of the current node's value
        freq[node->val]++;
 
        // If it's a leaf node, check for pseudo-palindromic path
        int count = 0;
        if (!node->left && !node->right) {
            if (isPseudoPalindromic(freq)) count = 1;
        }
 
        // Recur for left and right subtrees
        count += dfs(node->left, freq);
        count += dfs(node->right, freq);
 
        // Backtrack: Decrement the frequency before returning
        freq[node->val]--;
 
        return count;
    }
 
    bool isPseudoPalindromic(const vector<int>& freq) {
        int oddCount = 0;
        for (int f : freq) {
            if (f % 2 != 0) oddCount++;
            if (oddCount > 1) return false; // More than one odd count, not pseudo-palindromic
        }
        return true;
    }
};

Graph View