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

SimplyLeet
TagsCompaniesDisclaimersPrivacyTermsContactAbout Us

Pseudo-Palindromic Paths in a Binary Tree

Number: 1568

Difficulty: Medium

Paid? No

Companies: Amazon, Bloomberg

Problem Description

Given a binary tree where node values are digits from 1 to 9, count all root-to-leaf paths that are pseudo-palindromic. A path is pseudo-palindromic if at least one permutation of the node values in that path forms a palindrome. In other words, the path is pseudo-palindromic if at most one digit has an odd frequency.

Key Insights

  • Use Depth-First Search (DFS) to explore every root-to-leaf path.
  • Track the occurrence (odd/even) of digits using a bit mask, where each of the bits (positions 1 to 9) represents a digit.
  • Toggle bits using the XOR operation to update parity as you traverse the tree.
  • A path qualifies as pseudo-palindromic if the bit mask has at most one bit set (check using path & (path - 1) == 0).
  • This approach efficiently checks the pseudo-palindromic condition in O(1) time per leaf.

Space and Time Complexity

Time Complexity: O(N), where N is the number of nodes in the tree, as each node is visited once. Space Complexity: O(H), where H is the height of the tree. In the worst case, H equals N.

Solution

The solution uses a recursive DFS to traverse the tree while propagating a bit mask representing the parity of each digit encountered. At each node, update the bit mask by toggling the bit corresponding to the node's value. When a leaf is reached, check if the path is pseudo-palindromic by ensuring that at most one bit in the mask is set. This optimal approach leverages bit manipulation to keep the space usage minimal while ensuring a fast constant-time check at each leaf node.

Code Solutions

# Definition for a binary tree node.
# class TreeNode:
#     def __init__(self, val=0, left=None, right=None):
#         self.val = val
#         self.left = left
#         self.right = right

class Solution:
    def pseudoPalindromicPaths(self, root: TreeNode) -> int:
        # Total count of pseudo-palindromic paths
        count = 0
        
        # DFS helper function
        def dfs(node, path):
            nonlocal count
            if not node:
                return
            # Toggle the bit for the current node's value using XOR
            path ^= (1 << node.val)
            # If it is a leaf, check if the bit mask indicates a pseudo-palindrome
            if not node.left and not node.right:
                # Check if at most one bit is set in path (pseudo-palindromic condition)
                if path & (path - 1) == 0:
                    count += 1
            else:
                # Continue DFS on left and right children
                dfs(node.left, path)
                dfs(node.right, path)
        
        # Start DFS with path = 0
        dfs(root, 0)
        return count
← Back to All Questions