Pseudo palindromic paths in a binary tree

Bit Manipulation Tree Depth-First Search Breadth-First Search Binary Tree

68.4% acceptance

Feb 25, 2026

3338

131

Given a binary tree where node values are digits from 1 to 9. A path in the binary tree is called 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

Rust

Time O(n)

Space O(n)

LeetCode

solution.rs

use std::rc::Rc;
use std::cell::RefCell;
impl Solution {
  pub fn pseudo_palindromic_paths(root: Option<Rc<RefCell<TreeNode>>>) -> i32 {
    fn dfs(node: Option<Rc<RefCell<TreeNode>>>, mask: u32) -> i32 {
      if let Some(n) = node {
        let n = n.borrow();
        let mask = mask ^ (1 << n.val);
        if n.left.is_none() && n.right.is_none() {
          return if mask == 0 || (mask & (mask - 1)) == 0 { 1 } else { 0 };
        }
        dfs(n.left.clone(), mask) + dfs(n.right.clone(), mask)
      } else {
        0
      }
    }
    dfs(root, 0)
  }
}