Leetcode 1457. Pseudo-Palindromic Paths in a Binary Tree

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.

Approach 1: Iterative Preorder Traversal.


class Solution {
    public int pseudoPalindromicPaths (TreeNode root) {
        int count = 0, path = 0;
        
        Deque> stack = new ArrayDeque();
        stack.push(new Pair(root, 0));
        while (!stack.isEmpty()) {
            Pair p = stack.pop();
            TreeNode node = p.getKey();
            path = p.getValue();

            if (node != null) {
                // compute occurrence of each digit 
                // in the corresponding register
                path = path ^ (1 << node.val);
                // if it's a leaf check if the path is pseudo-palindromic
                if (node.left == null && node.right == null) {
                    // check if at most one digit has an odd frequency
                    if ((path & (path - 1)) == 0) {
                        ++count;
                    }
                } else {
                    stack.push(new Pair(node.right, path));
                    stack.push(new Pair(node.left, path));
                }
            }
        }
        return count;
    }
}

Time Complexity: O(n) and Space Complexity: O(n)

Approach 2: Recursive Preorder Traversal:


class Solution {
    int count = 0;
        
    public void preorder(TreeNode node, int path) {
        if (node != null) {
            // compute occurences of each digit 
            // in the corresponding register
            path = path ^ (1 << node.val);
            // if it's a leaf check if the path is pseudo-palindromic
            if (node.left == null && node.right == null) {
                // check if at most one digit has an odd frequency
                if ((path & (path - 1)) == 0) {
                    ++count;
                }
            }
            preorder(node.left, path);
            preorder(node.right, path) ;
        }
    }

    public int pseudoPalindromicPaths (TreeNode root) {
        preorder(root, 0);
        return count;
    }
}

Time Complexity: O(n) and Space Complexity: O(n)

Introduction

The "Pseudo-Palindromic Paths in a Binary Tree" problem is about finding the number of paths in a binary tree where the values of the nodes along the path form a pseudo-palindrome. A pseudo-palindrome is a sequence of numbers where at most one number occurs an odd number of times. In other words, a path can be rearranged to form a palindrome if, and only if, no more than one value occurs an odd number of times in the path.

The binary tree is given as a set of nodes with integer values, and we need to check the paths from the root to the leaves, counting how many of them are pseudo-palindromes.

Problem Statement

Given a binary tree where each node has an integer value, count the number of pseudo-palindromic paths from the root to any leaf. A path is considered pseudo-palindromic if at most one value occurs an odd number of times along the path.

        class TreeNode:
            def __init__(self, val=0, left=None, right=None):
                self.val = val
                self.left = left
                self.right = right

The tree node structure is given above. We need to find how many paths from the root to the leaves are pseudo-palindromes.

Approach

The key to solving this problem is recognizing that a pseudo-palindrome can be determined by tracking the frequency of node values along a path. A path is pseudo-palindromic if there is at most one value that occurs an odd number of times. This can be tracked efficiently using a bitmask, where each bit represents the frequency of a particular node value along the path.

Here's how we can approach the problem:

Start at the root of the tree and traverse each path down to the leaves.
For each node visited, flip the bit corresponding to its value in a bitmask. The bitmask will help track how many times each node's value has appeared in the current path.
If we reach a leaf node, check if the bitmask has at most one bit set. If it does, the path is pseudo-palindromic.
Return the count of pseudo-palindromic paths once the traversal is complete.

Algorithm

The algorithm can be described as follows:

Start with the root node, initialize an empty bitmask, and perform a depth-first search (DFS) traversal of the tree.
At each node, flip the corresponding bit in the bitmask to reflect the inclusion of that node's value in the current path.
If a leaf node is reached, check if the bitmask has at most one bit set. If so, it means the path is pseudo-palindromic, and we count it.
After traversing all the paths from the root to the leaves, return the total count of pseudo-palindromic paths.

The bitmask technique ensures that we efficiently track the frequency of each node value along the path, and checking whether the path is pseudo-palindromic becomes a constant-time operation.

Example

Consider the following binary tree:

In this example, the binary tree has multiple paths from the root to the leaves. We need to check each path: - Path 1: 2 → 3 → 3 (this is a pseudo-palindrome) - Path 2: 2 → 3 → 1 → 1 (this is a pseudo-palindrome) - Path 3: 2 → 1 → 1 (this is a pseudo-palindrome)

All three paths are pseudo-palindromes. Therefore, the number of pseudo-palindromic paths in this tree is 3.

Code Implementation

Below is the Python implementation of the algorithm to count pseudo-palindromic paths in a binary tree:

class TreeNode:
    def __init__(self, val=0, left=None, right=None):
        self.val = val
        self.left = left
        self.right = right

def pseudoPalindromicPaths(root):
    def dfs(node, bitmask):
        if not node:
            return 0

        # Flip the bit corresponding to the node's value
        bitmask ^= (1 << node.val)

        # If it's a leaf, check if the path is pseudo-palindromic
        if not node.left and not node.right:
            return 1 if bin(bitmask).count('1') <= 1 else 0

        # Recurse on left and right subtrees
        return dfs(node.left, bitmask) + dfs(node.right, bitmask)

    return dfs(root, 0)

In this code: - The `dfs` function performs a depth-first search to traverse the tree. It keeps track of the bitmask that represents the frequencies of node values along the path. - At each leaf node, the function checks if the path is pseudo-palindromic by counting the number of bits set in the bitmask (using `bin(bitmask).count('1')`). - If there is at most one bit set, the path is pseudo-palindromic, and we increment the count.

Time Complexity

The time complexity of this algorithm is O(n), where n is the number of nodes in the binary tree. Each node is visited once during the DFS traversal.

The space complexity is O(h), where h is the height of the tree. This is due to the recursion stack used in the DFS traversal, where the maximum depth corresponds to the height of the tree.

Conclusion

The "Pseudo-Palindromic Paths in a Binary Tree" problem is an interesting application of bit manipulation combined with tree traversal. By using a bitmask to track the frequencies of node values along a path, we can efficiently determine if a path is pseudo-palindromic. This problem tests your understanding of tree traversal techniques and bitwise operations.