Teaching Kids Programming – Pseudo-Palindromic Paths in a Binary Tree (Recursive Depth First Search Algorithm)

Teaching Kids Programming: Videos on Data Structures and Algorithms

1457. Pseudo-Palindromic Paths in a Binary Tree

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

Pseudo-Palindromic Paths in a Binary Tree (Recursive Depth First Search Algorithm)

We need to collect all the elements when we walk from the root node down to any leaves nodes and count their frequencies. As long as we have at most one element which appears odd number of times, we can make a palindrome. We can perform a Recursive Depth First Search Algorithm to traverse the binary tree.

We use a static array of size 9 to count the frequencies for digits of 1-9. We don’t actually need to count, we can toggle the boolean flag to indicate a digit appears even or odd number of times. This can be done via the XOR (Exclusive Operator ^).

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17

class Solution:
    def pseudoPalindromicPaths (self, root: TreeNode) -> int:
 
        def dfs(root, arr):
            if not root:
                return 0
            arr[root.val - 1] ^= 1
            ans = dfs(root.left, arr[:])
            ans += dfs(root.right, arr[:])
            ## if this is a leaf node
            if root.left == root.right == None:
                ## at most one element appears odd number of time
                if sum(arr) <= 1:
                    ans += 1
            return ans
 
        return dfs(root, [0] * 9)

class Solution:
    def pseudoPalindromicPaths (self, root: TreeNode) -> int:

        def dfs(root, arr):
            if not root:
                return 0
            arr[root.val - 1] ^= 1
            ans = dfs(root.left, arr[:])
            ans += dfs(root.right, arr[:])
            ## if this is a leaf node
            if root.left == root.right == None:
                ## at most one element appears odd number of time
                if sum(arr) <= 1:
                    ans += 1
            return ans

        return dfs(root, [0] * 9)

Another optimal solution/implementation is to use a single integer to represent the 9 states. And each digit is represented as a bit e.g. 2^(d-1). As long as we walk down the binary tree, we update the state value (which contains 9 boolean bits, indicating the odd or even for digits 1-9). And when we reach any leave node, we check if the mask/flag is zero or power of two (which contains only 1 set bit, meaning at most 1 element appears odd number of times).

1
2
3
4
5
6
7
8
9
10
11
12
13
14

class Solution:
    def pseudoPalindromicPaths (self, root: TreeNode) -> int:
 
        def dfs(root, mask = 0):
            if not root:
                return 0
            mask ^= 1 << (root.val - 1)
            ans = dfs(root.left, mask) + dfs(root.right, mask)
            if root.left == root.right == None:
                if mask & (mask - 1) == 0:
                    ans += 1
            return ans
 
        return dfs(root)

class Solution:
    def pseudoPalindromicPaths (self, root: TreeNode) -> int:

        def dfs(root, mask = 0):
            if not root:
                return 0
            mask ^= 1 << (root.val - 1)
            ans = dfs(root.left, mask) + dfs(root.right, mask)
            if root.left == root.right == None:
                if mask & (mask - 1) == 0:
                    ans += 1
            return ans

        return dfs(root)

To check if a integer is power of two (only 1 bit is set), we can do this:

1
2

def is_power_of_two(n):
    return n > 0 and ((n & (n - 1)) == 0))

def is_power_of_two(n):
    return n > 0 and ((n & (n - 1)) == 0))

We can also solve this using the Breadth First Search Algorithm, or other DFS traversal orders such as Preorder and Reversed Preorder: Teaching Kids Programming – Pseudo-Palindromic Paths in a Binary Tree (Breadth First Search Algorithm, Iterative Preorder/Reversed Preorder)

–EOF (The Ultimate Computing & Technology Blog) —