Pseudo-Palindromic Paths in a Binary Tree

Medium
1951.

Pseudo-Palindromic Paths in a Binary Tree

Pseudo-Palindromic Paths in a Binary Tree is a medium coding problem on depth-first search, trees and bit manipulation, asked in Amazon and Google interviews.

You are given the root of a binary tree whose node values are digits from 1 to 9.

A root-to-leaf path is pseudo-palindromic if its values can be rearranged into a palindrome (a sequence that reads the same forwards and backwards). Return the number of pseudo-palindromic paths from the root to a leaf.

Example 1

Input
root = [2,3,1,3,1,null,1]
Output
2
Explanation
The paths are 2-3-3, 2-3-1 and 2-1-1. 2-3-3 can become 3-2-3 and 2-1-1 can become 1-2-1; 2-3-1 cannot be rearranged into a palindrome.

Example 2

Input
root = [2,1,1,1,3,null,null,null,null,null,1]
Output
1
Explanation
Of the paths 2-1-1, 2-1-3-1 and 2-1, only 2-1-1 (as 1-2-1) works.

Example 3

Input
root = [9]
Output
1
Explanation
A single digit is a palindrome.

Constraints

  • 1 <= number of nodes <= 10^5
  • 1 <= Node.val <= 9
Write your solution here. Running it against the tests needs a free account — what you type comes with you.Sign in to run
/**
 * Definition for a binary tree node (provided by the judge — do not redefine it):
 * function TreeNode(val, left, right) {
 *     this.val = (val===undefined ? 0 : val)
 *     this.left = (left===undefined ? null : left)
 *     this.right = (right===undefined ? null : right)
 * }
 */
/**
 * @param {TreeNode} root
 * @return {number}
 */
var pseudoPalindromicPaths = function(root) {
    // Write your code here
    
};

Sign in to run your own test cases

Sign in

Pseudo-Palindromic Paths in a Binary Tree — Solution

Pseudo-Palindromic Paths in a Binary Tree solution explained: step-by-step approach, complexity and code in Python, Java, C++ and JavaScript.

Pseudo-Palindromic Paths in a Binary Tree is a medium coding problem on depth-first search, trees and bit manipulation, asked in Amazon and Google interviews.

Problem statement

You are given the root of a binary tree whose node values are digits from 1 to 9.

A root-to-leaf path is pseudo-palindromic if its values can be rearranged into a palindrome (a sequence that reads the same forwards and backwards). Return the number of pseudo-palindromic paths from the root to a leaf.

Example 1

Input: root = [2,3,1,3,1,null,1]
Output: 2
Explanation: The paths are 2-3-3, 2-3-1 and 2-1-1. 2-3-3 can become 3-2-3 and 2-1-1 can become 1-2-1; 2-3-1 cannot be rearranged into a palindrome.

Example 2

Input: root = [2,1,1,1,3,null,null,null,null,null,1]
Output: 1
Explanation: Of the paths 2-1-1, 2-1-3-1 and 2-1, only 2-1-1 (as 1-2-1) works.

Example 3

Input: root = [9]
Output: 1
Explanation: A single digit is a palindrome.

Constraints

  • 1 <= number of nodes <= 10^5
  • 1 <= Node.val <= 9

Hints for Pseudo-Palindromic Paths in a Binary Tree

  1. Hint 1

    A multiset of digits can be arranged into a palindrome exactly when at most one digit appears an odd number of times.

  2. Hint 2

    So along a path you only need each digit's count parity — nine bits.

  3. Hint 3

    Toggle bit val on the way down; at a leaf the path qualifies when the mask has at most one set bit, i.e. mask & (mask - 1) == 0.

How to solve Pseudo-Palindromic Paths in a Binary Tree

Track, for each digit, whether it has appeared an odd number of times on the current path, as one bitmask. A path is pseudo-palindromic when at most one bit is set at its leaf.

Approach

  1. Walk depth-first from the root with mask = 0.
  2. At each node flip bit node.val: mask ^= 1 << node.val.
  3. At a leaf, count the path if mask & (mask - 1) == 0 (zero or one bit set).
  4. Otherwise continue into both children with the current mask and add their counts.

Why it works

A palindrome pairs up equal values around the centre, so every value appears an even number of times except possibly one (the centre). Conversely, with at most one odd count the pairs can be placed symmetrically and the odd one in the middle. Flipping a bit per occurrence records exactly the parity of each count.

Complexity

  • Time — O(n)
  • Space — O(h) for the recursion

Pitfalls

  • Only root-to-leaf paths count — do not test the mask at inner nodes.
  • Pass the mask by value (or undo the flip when returning); a shared mask leaks between branches.

Reference solution

Python

from typing import Optional

def pseudoPalindromicPaths(root: Optional[TreeNode]) -> int:
    def walk(node, mask):
        mask ^= 1 << node.val
        if node.left is None and node.right is None:
            return 1 if mask & (mask - 1) == 0 else 0
        total = 0
        if node.left:
            total += walk(node.left, mask)
        if node.right:
            total += walk(node.right, mask)
        return total

    return walk(root, 0)

Java

public static int pseudoPalindromicPaths(TreeNode root) {
    return palWalk(root, 0);
}

static int palWalk(TreeNode node, int mask) {
    mask ^= 1 << node.val;
    if (node.left == null && node.right == null) return (mask & (mask - 1)) == 0 ? 1 : 0;
    int total = 0;
    if (node.left != null) total += palWalk(node.left, mask);
    if (node.right != null) total += palWalk(node.right, mask);
    return total;
}

C++

int palWalk(TreeNode* node, int mask);

int pseudoPalindromicPaths(TreeNode* root) {
    return palWalk(root, 0);
}

int palWalk(TreeNode* node, int mask) {
    mask ^= 1 << node->val;
    if (!node->left && !node->right) return (mask & (mask - 1)) == 0 ? 1 : 0;
    int total = 0;
    if (node->left) total += palWalk(node->left, mask);
    if (node->right) total += palWalk(node->right, mask);
    return total;
}

JavaScript

var pseudoPalindromicPaths = function(root) {
    return palWalk(root, 0);
};

var palWalk = function(node, mask) {
    mask ^= 1 << node.val;
    if (node.left === null && node.right === null) return (mask & (mask - 1)) === 0 ? 1 : 0;
    var total = 0;
    if (node.left !== null) total += palWalk(node.left, mask);
    if (node.right !== null) total += palWalk(node.right, mask);
    return total;
};

Also on the editorial tab: C, C#, Go, Kotlin, PHP, Ruby, Rust, Swift, TypeScript.

All 201 depth-first search problems · the whole catalogue

Learn the technique: Depth-First Search (DFS) · Binary Trees and Tree Traversals