Problem 1457

Question statement

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.

Solution

DFS time!

Main idea:

Key observation: A sequence of numbers can potentially be a palindrome if at most one of the numbers occurs an odd number of times.

Traverse the tree in a dfs fashion and recurse until reaching a leaf node all the while keeping track of a dictionary of all visited nodes in the current path. Once a leaf node is reached, check for key observation, and if true, add one to a counter. Now if at any node both the right and left subtrees have been explored, decrement the frequency of the current node in our dictionary by 1 (effectively removing it from the path). Programattically, this is done after the left and right recursive function calls. Finally, return count.

Code:

def dfs(self, root, count, freq):
    if root == None:
        return count 
        
    freq[root.val] += 1
    
    if(root.left == None and root.right == None):
        odd_freq = 0
        for i in freq.values():
            if(i%2 == 1):
                odd_freq+=1
        if(odd_freq <= 1):
            count+=1

    count = self.dfs(root.left, count, freq)
    count = self.dfs(root.right, count, freq)
    if(not freq):
        return  count
    
    freq[root.val]-=1
    return count

    def pseudoPalindromicPaths (self, root: Optional[TreeNode]) -> int:
        
        return self.dfs(root, 0, defaultdict(int))

Comments:

Time complexity: O(n)
Note that the inner for loop doesn’t affect the time complexity since freq.keys can have at most 9 elements – and hence the for loop has a fixed run time independent of n.

At the time of submission, the above solution passes leetcode submission cases in 406ms, beating 89.20% of users. It uses 43.50MB of memory, beating 98.12% of users.