Teaching Kids Programming – Pseudo-Palindromic Paths in a Binary Tree (Breadth First Search Algorithm, Iterative Preorder/Reversed Preorder)

Teaching Kids Programming: Videos on Data Structures and Algorithms

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

We can also solve this problem by Depth First Search Algorithm: Teaching Kids Programming – Pseudo-Palindromic Paths in a Binary Tree (Recursive Depth First Search Algorithm)

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

BFS (Breadth First Search) is another classic way of traversing a Tree (or Graph). BFS performs the tree traversal level by level. For this problem, as long as we carry the mask information (the nodes and their odd/even occurrence from root to leaves nodes), the order of tree traversal does not matter.

We use a queue (double-ended queue to achieve O(1) constant push/pop from both sides of the queue), to implement a Breadth First Search. The node value and the current mask is enqueued and dequeued. The following Python code performs a BFS with O(N) time and O(N) space as we need to traverse the entire binary tree with N nodes, and the space requirement is due to the usage of a double-ended queue.

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

class Solution:
    def pseudoPalindromicPaths (self, root: TreeNode) -> int:
        ans = 0
        q = deque([(root, 0)])
        while q:
            cur, mask = q.popleft()
            mask ^= (1 << cur.val)
            if cur.left == cur.right == None:
                if mask & (mask - 1) == 0:
                    ans += 1
            else:                
                if cur.left:
                    q.append((cur.left, mask))
                if cur.right:
                    q.append((cur.right, mask))
        return ans

class Solution:
    def pseudoPalindromicPaths (self, root: TreeNode) -> int:
        ans = 0
        q = deque([(root, 0)])
        while q:
            cur, mask = q.popleft()
            mask ^= (1 << cur.val)
            if cur.left == cur.right == None:
                if mask & (mask - 1) == 0:
                    ans += 1
            else:                
                if cur.left:
                    q.append((cur.left, mask))
                if cur.right:
                    q.append((cur.right, mask))
        return ans

Pseudo-Palindromic Paths in a Binary Tree (Preorder and Reversed Preorder Traversal using Iterative DFS)

If we use a list to emulate the stack, and change the popleft to pop (e.g. pop from right), it is a Depth First Search, but in the order of NRL – which is reversed pre-order, but we can swap around the left/right nodes i.e. push the right node first and then left node, then we get a pre-order traversal using iterative approach.

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

class Solution:
    def pseudoPalindromicPaths (self, root: TreeNode) -> int:
        ans = 0
        st = [(root, 0)]
        while st:
            cur, mask = st.pop()
            mask ^= (1 << cur.val)
            if cur.left == cur.right == None:
                if mask & (mask - 1) == 0:
                    ans += 1
            else:
                ## push the right node so the left node is pop next
                ## NLR = Pre order Traversal
                if cur.right:
                    st.append((cur.right, mask))
                if cur.left:
                    st.append((cur.left, mask))
        return ans

class Solution:
    def pseudoPalindromicPaths (self, root: TreeNode) -> int:
        ans = 0
        st = [(root, 0)]
        while st:
            cur, mask = st.pop()
            mask ^= (1 << cur.val)
            if cur.left == cur.right == None:
                if mask & (mask - 1) == 0:
                    ans += 1
            else:
                ## push the right node so the left node is pop next
                ## NLR = Pre order Traversal
                if cur.right:
                    st.append((cur.right, mask))
                if cur.left:
                    st.append((cur.left, mask))
        return ans

This is the iterative implementation of the Depth First Search Algorithm: Teaching Kids Programming – Pseudo-Palindromic Paths in a Binary Tree (Recursive Depth First Search Algorithm)

–EOF (The Ultimate Computing & Technology Blog) —