Count longest subsequence in binary tree

Question

Given a binary tree, write a function to count the number of longest increasing subsequences from the root to any leaf node. The function should take the root node of the binary tree as input and return an integer representing the count of such subsequences. Each path from the root to a leaf node is considered a subsequence, and only those that are strictly increasing should be counted.

Codemia · Accepted Answer

This problem involves traversing a binary tree and identifying the longest increasing subsequences from the root to any leaf node. The key pattern here is DFS (Depth-First Search) because we need to explore each path from the root to the leaves recursively. We will check for increasing subsequences while traversing, which makes it suitable for recursive exploration. Each path can be considered a sequence, and we need to keep track of the longest ones.

1. **Depth-First Search (DFS)**: We will implement a recursive function that explores each path from the root to the leaves. 
2. **Tracking Subsequences**: As we traverse, we will maintain two pieces of information: the length of the current increasing subsequence and the count of the longest increasing subsequences found. 
3. **Base Case**: When we reach a leaf node, we will check if the current length of the subsequence is greater than the maximum found so far, and if so, we update our count. If it equals the maximum, we increment our count. 
4. **Example**: For a tree like: 
   
        1  
       / \ 
      2   3  
     / 
    4  
   
   The paths are [1, 2, 4] and [1, 3]. The longest increasing subsequence is of length 3 and we have 1 such subsequence.

Here is the Python solution to the problem:
```python
class TreeNode:
    def __init__(self, value=0, left=None, right=None):
        self.value = value
        self.left = left
        self.right = right

def countLongestIncreasingSubsequences(root):
    if not root:
        return 0

max_length = 0
    count = 0

def dfs(node, prev_value, length):
        nonlocal max_length, count
        if not node:
            return
        if node.value > prev_value:
            length += 1
        else:
            length = 1

# If it's a leaf node
        if not node.left and not node.right:
            if length > max_length:
                max_length = length
                count = 1
            elif length == max_length:
                count += 1
        else:
            dfs(node.left, node.value, length)
            dfs(node.right, node.value, length)

dfs(root, float('-inf'), 0)
    return count
```

The **time complexity** of this solution is O(n), where n is the number of nodes in the binary tree. This is because we visit each node once during the DFS traversal. The **space complexity** is O(h), where h is the height of the tree, due to the recursive call stack. In the worst case (for a skewed tree), h could be n, but for a balanced tree, it would be log(n). Given that trees are usually balanced, the space complexity can be considered efficient.

1. **Empty Tree**: If the root is None, we should return 0 as there are no subsequences. 
2. **Single Node Tree**: If the tree has only one node, the count should be 1 since the only path is the node itself. 
3. **All Nodes Increasing**: If all nodes are in an increasing order, the count should reflect all paths. 
4. **All Nodes Decreasing**: In this case, no increasing subsequences should be counted, resulting in 0.
5. **Mixed Values**: Trees where nodes have both increasing and decreasing values along different paths should be handled accurately to ensure correct counting.

Count longest subsequence in binary tree

Visa

What the Interviewer Expects

Key Topics to Cover

How to Approach This

Possible Follow-up Questions

Sharpen Your Skills on Codemia

Sample Answer

Problem Analysis

Approach

Submit Your Answer

Visa Software Engineer Interview Guide

Related Questions

Binary Search on graph

Count kth largest element in array

Find connected components in string

Merge Three Sorted strings

Binary Search on string