We use cookies (including Google cookies) to personalize ads and analyze traffic. By continuing to use our site, you accept our Privacy Policy.

SimplyLeet
TagsDisclaimersPrivacyTermsContactAbout Us

Pseudo-Palindromic Paths in a Binary Tree

Difficulty: Medium

Problem Description

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.

Key Insights

  • A path can be considered pseudo-palindromic if at most one digit has an odd count, as this allows for a potential palindrome arrangement.
  • The problem can be solved using Depth-First Search (DFS) to traverse the tree and keep track of the counts of each digit.
  • Leaf nodes are the end of paths, and we need to check the counts at these nodes to determine if the path is pseudo-palindromic.

Space and Time Complexity

Time Complexity: O(N), where N is the number of nodes in the tree, as we visit each node once.

Space Complexity: O(H), where H is the height of the tree, due to the recursive stack used in DFS.

Solution

The solution involves a Depth-First Search approach. We traverse the binary tree while maintaining a count of the occurrences of each digit (1-9) using a frequency array or bit manipulation. When we reach a leaf node, we check the frequency of each digit to determine if it can form a pseudo-palindrome by counting how many digits have an odd frequency. If more than one digit has an odd count, the path is not pseudo-palindromic.

Code Solutions

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

def pseudoPalindromicPaths(root: TreeNode) -> int:
    def dfs(node, count):
        if not node:
            return 0
        
        # Toggle the bit corresponding to the node's value
        count ^= (1 << node.val)
        
        # If it's a leaf node, check the number of odd counts
        if not node.left and not node.right:
            # Check if at most one bit is set in count
            if count & (count - 1) == 0:
                return 1
            return 0
        
        # Continue DFS on left and right children
        return dfs(node.left, count) + dfs(node.right, count)

    return dfs(root, 0)
← Back to All Questions