Pseudo-Palindromic Paths in a Binary Tree

Medium

Asked by:

32 views

Topics:

TreesRecursionBit Manipulation

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, 10⁵].
1 <= Node.val <= 9

Try coding it in LeetCode

Solution

Clarifying Questions

When you get asked this question in a real-life environment, it will often be ambiguous (especially at FAANG). Make sure to ask these questions in that case:

What is the range of values that each node in the binary tree can have?
Can the binary tree be empty? What should I return if it is?
By 'pseudo-palindromic', do you mean that at most one digit along the path has an odd frequency?
Are the node values guaranteed to be single digits (0-9)?
Are we only concerned with paths from the root to a leaf node, or should all possible paths be considered?

Brute Force Solution

Approach

The brute force method for this problem involves exploring every single possible path from the top of the tree to the bottom. For each path, we will check if it qualifies as a pseudo-palindrome, and count it if it does. We will explore every possible path and count the number of pseudo-palindromic ones.

Here's how the algorithm would work step-by-step:

Start at the very top of the tree (the root).
Follow one path down to a bottom leaf node.
As you travel down this path, keep track of the numbers you encounter along the way.
Once you reach the bottom, check if the list of numbers we collected can be rearranged to form a pseudo-palindrome. A pseudo-palindrome is a sequence where at most one number appears an odd number of times.
If the path is a pseudo-palindrome, add one to our count.
Now, go back to a point where you had a choice of paths and take a different direction.
Repeat this process of exploring a path, checking for pseudo-palindromes, and counting them for every possible path from the top to a bottom leaf node.
Finally, once you've explored every single possible path, report the total count of pseudo-palindromic paths you found.

Code Implementation

def pseudo_palindromic_paths(root):
    number_of_pseudo_palindromic_paths = 0

    def is_pseudo_palindrome(path):
        counts = {}
        for node_value in path:
            counts[node_value] = counts.get(node_value, 0) + 1

        odd_count = 0
        for node_value in counts:
            if counts[node_value] % 2 != 0:
                odd_count += 1

        return odd_count <= 1

    def dfs(node, current_path):
        nonlocal number_of_pseudo_palindromic_paths

        if not node:
            return

        current_path.append(node.val)

        #  If it's a leaf node, check for pseudo-palindrome.
        if not node.left and not node.right:
            if is_pseudo_palindrome(current_path):
                number_of_pseudo_palindromic_paths += 1
        else:
            dfs(node.left, current_path)
            dfs(node.right, current_path)

        # Backtrack by removing current node from path.
        current_path.pop()

    dfs(root, [])

    return number_of_pseudo_palindromic_paths

Big(O) Analysis

Time Complexity

O(N) – The brute force approach explores every path from the root to a leaf node in the binary tree. In the worst-case scenario, where the tree is complete, there can be up to N/2 leaf nodes and approximately N total nodes where N is the number of nodes in the tree. Each path from root to leaf has a length proportional to the height of the tree, which is log(N) in a balanced tree or N in a skewed tree. The pseudo-palindrome check for each path takes O(number of digits which is constant in this case as digits are only from 1-9), so it can be regarded as constant time. Therefore, the algorithm explores all the nodes in the tree once, and since the pseudo-palindrome check takes constant time, the overall time complexity is O(N).

Space Complexity

O(H) – The space complexity is determined by the maximum depth of the recursion stack, where each level of recursion corresponds to a node in the path from the root to a leaf. In the worst case, the tree could be skewed, resulting in a maximum recursion depth equal to the height (H) of the tree. Additionally, each recursive call maintains a path, so in the worst-case scenario where H is close to N (the number of nodes), the space used could be O(N). Therefore, the auxiliary space is O(H), where H is the height of the tree.

Optimal Solution

Approach

The problem asks us to count paths from the top of a tree to its leaves where, along each path, the counts of the numbers are 'almost' a palindrome. To avoid checking for a pseudo-palindrome at every leaf, we'll track the counts of the numbers encountered so far using clever shortcut. This makes the process much faster.

Here's how the algorithm would work step-by-step:

Start at the very top of the tree, which is the root.
Keep track of how many times we've seen each number as we travel down a path from the top to a leaf. Think of it as a running tally for each number.
When we reach a leaf (the end of a path), check if the path is 'almost' a palindrome. 'Almost' means that at most one number appears an odd number of times. All other numbers must appear an even number of times.
Instead of actually building a palindrome and checking it, we can just count how many numbers along the path appear an odd number of times. If that count is zero or one, the path is pseudo-palindromic.
For each node we visit on a path, cleverly update our running count of numbers. The clever part is to use a trick where we can both add and remove counts easily when we go down a path and then backtrack up the tree.
If we visit a leaf and find a pseudo-palindromic path, increase our total count of such paths.
After visiting each leaf, carefully backtrack up the tree, undoing the changes to our running counts as we go. This ensures that when we explore a different path, we start with the correct counts.
Continue exploring all possible paths from the root to each leaf, accumulating the count of pseudo-palindromic paths until all leaves are checked.

Code Implementation

class TreeNode:
    def __init__(self, val=0, left=None, right=None):
        self.val = val
        self.left = left
        self.right = right

def pseudoPalindromicPaths (root: TreeNode) -> int:
    number_counts = [0] * 10
    pseudo_palindrome_count = 0

    def dfs(node: TreeNode):
        nonlocal pseudo_palindrome_count
        number_counts[node.val] += 1

        if not node.left and not node.right:
            # We've reached a leaf node; check pseudo-palindrome condition.
            odd_count = 0
            for count in number_counts:
                if count % 2 != 0:
                    odd_count += 1

            # Increment the palindrome count if condition is met
            if odd_count <= 1:
                pseudo_palindrome_count += 1
        else:
            # Explore the left subtree if it exists.
            if node.left:
                dfs(node.left)

            # Explore the right subtree if it exists.
            if node.right:
                dfs(node.right)

        # Backtrack: Decrement the count after visiting the node.
        number_counts[node.val] -= 1

    # Initiate the depth-first search from the root.
    if root:
        dfs(root)

    return pseudo_palindrome_count

Big(O) Analysis

Time Complexity

O(n) – The algorithm performs a Depth-First Search (DFS) traversal of the binary tree. In the worst-case scenario, it visits each of the n nodes in the tree exactly once. The operations performed at each node (updating counts, checking pseudo-palindrome condition which takes constant time using bit manipulation or an array of fixed size 10, backtracking) take constant time, O(1). Therefore, the overall time complexity is proportional to the number of nodes in the tree, resulting in O(n).

Space Complexity

O(H) – The primary contributor to auxiliary space is the recursion stack, where H is the height of the binary tree. In the worst-case scenario (a skewed tree), the recursion depth can reach N, where N is the number of nodes in the tree. However, in a balanced tree, the height would be log(N). Therefore, the space complexity is O(H), representing the maximum depth of the call stack.

Edge Cases

Case	How to Handle
Null root node	Return 0 if the root is null since there are no paths.
Single node tree	If it's a single node, check if its val is even; if so it's pseudo-palindromic, otherwise it is not.
All nodes have the same value	The path will be pseudo-palindromic if the depth is even or odd depending on that value's frequency count.
Highly unbalanced tree (skewed left or right)	Recursion depth can reach the maximum height of the tree, potentially leading to stack overflow if the tree is extremely unbalanced and large; consider iterative DFS or BFS.
Values outside the problem description's stated range (1 <= Node.val <= 9)	The frequency counter array must be resized according to the value range, or input validation must be enforced.
Maximum tree depth (test for stack overflow)	Consider iterative DFS or BFS to avoid exceeding call stack limitations for very deep trees.
Tree with no pseudo-palindromic paths	The algorithm should correctly return 0 when no path satisfies the pseudo-palindromic condition.
Large number of pseudo-palindromic paths	The algorithm must efficiently count each path and avoid integer overflow if the number of paths becomes excessively large.

Null root node

How to Handle:

Return 0 if the root is null since there are no paths.

Single node tree

How to Handle:

If it's a single node, check if its val is even; if so it's pseudo-palindromic, otherwise it is not.

All nodes have the same value

How to Handle:

The path will be pseudo-palindromic if the depth is even or odd depending on that value's frequency count.

Highly unbalanced tree (skewed left or right)

How to Handle:

Recursion depth can reach the maximum height of the tree, potentially leading to stack overflow if the tree is extremely unbalanced and large; consider iterative DFS or BFS.

Values outside the problem description's stated range (1 <= Node.val <= 9)

How to Handle:

The frequency counter array must be resized according to the value range, or input validation must be enforced.

Maximum tree depth (test for stack overflow)

How to Handle:

Consider iterative DFS or BFS to avoid exceeding call stack limitations for very deep trees.

Tree with no pseudo-palindromic paths

How to Handle:

The algorithm should correctly return 0 when no path satisfies the pseudo-palindromic condition.

Large number of pseudo-palindromic paths

How to Handle:

The algorithm must efficiently count each path and avoid integer overflow if the number of paths becomes excessively large.