1457. Pseudo-Palindromic Paths in a Binary Tree

Pseudo-Palindromic Paths in a Binary Tree (LeetCode 1457) is a Medium Data Structures and Algorithms interview problem you can solve, run and submit on Thita.ai. It belongs to the Backtracking Patterns pattern, in the Palindrome Partitioning subpattern.

How to solve Pseudo-Palindromic Paths in a Binary Tree

Pseudo-Palindromic Paths in a Binary Tree is a Palindrome Partitioning problem, part of Backtracking Patterns. Partition string into palindromic substrings using backtracking.

Work towards the solution in these steps:

1. Consider using a depth-first traversal technique to explore all root-to-leaf paths in the binary tree.
2. As you traverse, think about how to efficiently track the frequency of node values along the current path without storing the entire path.
3. Recall that a palindrome can have at most one character with an odd frequency count; how can this property help in checking pseudo-palindromic paths?

The reference solution runs in O(n) time and O(h) space.

The Pseudo-Palindromic Paths in a Binary Tree solution and editorial walks through the full approach with reference code.

Problem statement

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.

Example 1: Input: root = [2,3,1,3,1,null,1] Output: 2 Explanation: The figure above represents the given binary tree. There are three paths going from the root node to leaf nodes: the red path [2,3,3], the green path [2,1,1], and the path [2,3,1]. Among these paths only red path and green path are pseudo-palindromic paths since the red path [2,3,3] can be rearranged in [3,2,3] (palindrome) and the green path [2,1,1] can be rearranged in [1,2,1] (palindrome).

Example 2: Input: root = [2,1,1,1,3,null,null,null,null,null,1] Output: 1 Explanation: The figure above represents the given binary tree. There are three paths going from the root node to leaf nodes: the green path [2,1,1], the path [2,1,3,1], and the path [2,1]. Among these paths only the green path is pseudo-palindromic since [2,1,1] can be rearranged in [1,2,1] (palindrome).

Example 3: Input: root = [9] Output: 1

Constraints: The number of nodes in the tree is in the range [1, 105].

1 <= Node.val <= 9

Topics and companies

Topics: Bit Manipulation, Tree, Depth-first Search.

Reported in interviews at Amazon.

How to practise Pseudo-Palindromic Paths in a Binary Tree on Thita.ai

Starter code is provided in C, C#, C++, dart, elixir, erlang, Go, Java, JavaScript, Kotlin, PHP, Python, python3, racket, Ruby, Rust, Scala, Swift and TypeScript. Your solution runs against 5 test cases for this problem, with the AI coach available for a hint when you are stuck rather than a finished answer. The reference solution runs in O(n) time and O(h) space.

Open Pseudo-Palindromic Paths in a Binary Tree in the code editor, or read the Pseudo-Palindromic Paths in a Binary Tree editorial for a worked solution with its approach and complexity analysis.

Where Pseudo-Palindromic Paths in a Binary Tree sits in the DSA pattern sheet

• Backtracking Patterns pattern guide
• Palindrome Partitioning subpattern
• The full DSA patterns sheet

Problems related to Pseudo-Palindromic Paths in a Binary Tree

Other problems that use the same Palindrome Partitioning and Backtracking Patterns techniques:

• Palindrome Partitioning — Medium, same subpattern
• Palindrome Partitioning II — Hard, same subpattern
• Check if Word Can Be Placed In Crossword — Medium, same pattern
• Combinations — Medium, same pattern
• Combination Sum — Medium, same pattern
• Combination Sum II — Medium, same pattern

Pseudo-Palindromic Paths in a Binary Tree FAQ