{ }DevToolsDaily
ToolsInterview Prep
New
CheatsheetsDirectoryMy spaceBlog
Ctrl + K
Ask AI

Pseudo-Palindromic Paths in a Binary Tree – Solution & Complexity

Interview solutions
/
Pseudo-Palindromic Paths in a Binary Tree

Solution Walkthrough

  1. Step 1: Recognize the Pattern

    The key pattern is: root-to-leaf DFS that carries parity state instead of full frequency maps. Toggling one bit per digit lets you tell, at a leaf, whether at most one count is odd.

  2. Step 2: Build the Algorithm

    Advance one state transition at a time. XOR the current digit into the mask before exploring children, then test the final mask only when you reach a leaf.

  3. Step 3: Check Edge Cases

    Test empty or minimal input, skewed shapes, repeated digits that leave zero odd counts, and paths where two or more digits remain odd.

  4. Step 4: Solution and Complexity

    Time: O(n) — every node is visited once. Space: O(h) for the recursion stack, where h is the tree height (O(n) worst case on a skewed tree).

    All 7 languages below use the same DFS + bitmask idea: toggle bit digit - 1 on the way down, and at each leaf check whether mask & (mask - 1) == 0.

    def pseudo_palindromic_paths(root: TreeNode) -> int:
    def dfs(node: TreeNode, mask: int) -> int:
        if node is None:
            return 0

        mask ^= 1 << (node.val - 1)
        if node.left is None and node.right is None:
            return 1 if mask & (mask - 1) == 0 else 0

        return dfs(node.left, mask) + dfs(node.right, mask)

    return dfs(root, 0)

FAQ

See also

Practice Pseudo-Palindromic Paths in a Binary Tree online (run code in the browser)Balanced Binary Tree solution (easy)Binary Tree Inorder Traversal solution (easy)Binary Tree Maximum Path Sum solution (hard)Binary Tree Postorder Traversal solution (easy)All coding interview problems
Buy me a coffeePrivacyTermsFAQChangelogFeature RequestsBlogAll ToolsPricingContact Us © Monkey SkatesHave kids?