Jobs

Interviews

Discussions

Binary Tree Longest Consecutive Sequence

Medium

Amazon

1 view

Topics:

TreesRecursion

You are given the root of a binary tree. A consecutive sequence in a binary tree is a sequence of nodes where each node's value is exactly one greater than the previous node's value. The sequence can go in any direction, i.e., from parent to children or from children to parent.

Your task is to find the length of the longest consecutive sequence in the tree.

For example:

Example 1:
```
      1
       \
        2
         \
          3
```
The longest consecutive sequence is 1 -> 2 -> 3. The length is 3.
Example 2:
```
        2
       / \
      1   3
```
The longest consecutive sequence is 2 -> 3. The length is 2.
Example 3:
```
       1
      / \
     2   0
    /   /
   3   -1
```
The longest consecutive sequence is 0 -> -1. The length is 2. Another valid one is 1 -> 2 -> 3. The length is 3.

Write a function that takes the root of a binary tree as input and returns the length of the longest consecutive sequence.

Binary Tree Longest Consecutive Sequence

Medium

Amazon

1 view

Topics:

TreesRecursion

Your task is to find the length of the longest consecutive sequence in the tree.

For example:

Example 1:
```
      1
       \
        2
         \
          3
```
The longest consecutive sequence is 1 -> 2 -> 3. The length is 3.
Example 2:
```
        2
       / \
      1   3
```
The longest consecutive sequence is 2 -> 3. The length is 2.
Example 3:
```
       1
      / \
     2   0
    /   /
   3   -1
```
The longest consecutive sequence is 0 -> -1. The length is 2. Another valid one is 1 -> 2 -> 3. The length is 3.

Write a function that takes the root of a binary tree as input and returns the length of the longest consecutive sequence.

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:

Can the tree be empty? What should I return if it is?
Are the node values guaranteed to be integers, and can they be negative?
By 'longest consecutive sequence', do you mean strictly increasing by 1 at each step?
If there are multiple longest consecutive sequences of the same length, is it sufficient to return the length of any one of them?
Are we only considering paths from parent to child, or can a consecutive sequence go up to a parent node from a child?

Brute Force Solution

Approach

To find the longest consecutive sequence in a binary tree using a brute force method, we explore every possible path down the tree. We check each path to see if it forms a consecutive sequence, and then we keep track of the longest one we find.

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

Start at the very top of the tree.
Consider the path that just includes the top node itself. Check if this single node forms a consecutive sequence (which it always does, trivially).
Now, explore every possible path downwards. For each node, consider paths that go to its left child, and paths that go to its right child.
For each path you're exploring, check if the numbers in the path form a consecutive sequence, meaning each number is one greater than the previous number.
Keep track of the length of each consecutive sequence you find.
After exploring all possible paths in the tree, compare the lengths of all the consecutive sequences you found.
The longest consecutive sequence you encountered during your exploration is the answer.

Code Implementation

def binary_tree_longest_consecutive_sequence(root):
    longest_sequence_length = 0

    def explore_paths(node, current_sequence):
        nonlocal longest_sequence_length

        if not node:
            return

        # Check if the current node extends the sequence
        if not current_sequence or node.val == current_sequence[-1] + 1:
            current_sequence.append(node.val)
        else:
            current_sequence = [node.val]

        longest_sequence_length = max(longest_sequence_length, len(current_sequence))

        # Explore the left and right subtrees
        explore_paths(node.left, current_sequence[:])

        explore_paths(node.right, current_sequence[:])

    # Initiate the recursive traversal to find the longest sequence
    explore_paths(root, [])

    return longest_sequence_length

Big(O) Analysis

Time Complexity

O(n²) – The described brute force approach explores every possible path in the binary tree. In the worst-case scenario (a skewed tree resembling a linked list), there can be approximately n paths, where n is the number of nodes. For each of these n paths, we potentially iterate through all the nodes on that path, which could also be of length n in the worst case to check for consecutiveness. Therefore, the time complexity is approximately n * n, which simplifies to O(n²).

Space Complexity

O(N) – The brute force approach, as described, explores every possible path downwards. In the worst-case scenario, where the tree is skewed (e.g., a linked list), the recursion stack will grow to a depth of N, where N is the number of nodes in the tree. Each recursive call adds a new frame to the stack, consuming memory. Therefore, the auxiliary space used by the recursion stack is proportional to the number of nodes, resulting in O(N) space complexity.

Optimal Solution

Approach

We'll explore the tree by looking at each path from top to bottom. At each step, we check if the current node's value follows the consecutive sequence from its parent. This way, we only focus on promising sequences.

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

Begin at the very top of the tree, the root.
For each node, check if its value is exactly one more than its parent's value.
If it is, we're continuing a consecutive sequence, so we increase the length of the current sequence by one.
If it's not, we're starting a new sequence, so we reset the sequence length back to one.
As we travel through the tree, keep track of the longest consecutive sequence we've found so far.
Continue this process for every node in the tree.
The final longest length we tracked is the answer.

Code Implementation

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

def longest_consecutive(root):
    longest_sequence = 0

    def depth_first_search(node, parent_value, current_length):
        nonlocal longest_sequence

        if not node:
            return

        # Determine if current node continues sequence.
        if parent_value + 1 == node.value:
            current_length += 1
        else:
            # Reset sequence as it's not consecutive.
            current_length = 1

        # Update the longest sequence found so far.
        longest_sequence = max(longest_sequence, current_length)

        depth_first_search(node.left, node.value, current_length)

        # Explore the right subtree.
        depth_first_search(node.right, node.value, current_length)

    # Initiate the search at the root.
    depth_first_search(root, float('-inf'), 0)

    return longest_sequence

Big(O) Analysis

Time Complexity

O(n) – The algorithm performs a traversal of the binary tree, visiting each node exactly once. At each node, a constant amount of work is done: comparing the node's value to its parent's value and updating the maximum length if necessary. Since we visit each of the n nodes in the tree once, and the work at each node is constant, 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 recursive call represents a node being visited in the tree. In the worst-case scenario (e.g., a skewed tree), the recursion can go as deep as the height (H) of the tree, leading to H stack frames. Therefore, the auxiliary space required is proportional to the height of the tree. In the best case for a balanced tree, H is log(N), and in the worst case for a skewed tree, H is N, where N is the number of nodes in the tree.

Edge Cases

Case	How to Handle
Null root node	Return 0 immediately as an empty tree has no consecutive sequence.
Single node tree	Return 1 as a single node is a sequence of length 1.
Tree with all identical values	The longest consecutive sequence will be of length 1 because no consecutive numbers exist.
Left-skewed tree	The algorithm should correctly traverse and identify the longest consecutive sequence, possibly with increased stack depth if recursion is used.
Right-skewed tree	The algorithm should correctly traverse and identify the longest consecutive sequence, possibly with increased stack depth if recursion is used.
Very large tree (potential stack overflow with recursion)	Consider iterative approaches using a stack or queue to avoid stack overflow errors with deep trees.
Integer overflow if node values are extremely large	While unlikely given problem constraints, consider using larger integer types if node values could approach maximum integer values.
Tree with negative values that can form consecutive sequence	The algorithm should correctly handle negative values when checking for consecutive sequences by comparing to 'node.val + 1'.

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:

Can the tree be empty? What should I return if it is?
Are the node values guaranteed to be integers, and can they be negative?
By 'longest consecutive sequence', do you mean strictly increasing by 1 at each step?
If there are multiple longest consecutive sequences of the same length, is it sufficient to return the length of any one of them?
Are we only considering paths from parent to child, or can a consecutive sequence go up to a parent node from a child?

Brute Force Solution

Approach

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

Start at the very top of the tree.
Consider the path that just includes the top node itself. Check if this single node forms a consecutive sequence (which it always does, trivially).
Now, explore every possible path downwards. For each node, consider paths that go to its left child, and paths that go to its right child.
For each path you're exploring, check if the numbers in the path form a consecutive sequence, meaning each number is one greater than the previous number.
Keep track of the length of each consecutive sequence you find.
After exploring all possible paths in the tree, compare the lengths of all the consecutive sequences you found.
The longest consecutive sequence you encountered during your exploration is the answer.

Code Implementation

def binary_tree_longest_consecutive_sequence(root):
    longest_sequence_length = 0

    def explore_paths(node, current_sequence):
        nonlocal longest_sequence_length

        if not node:
            return

        # Check if the current node extends the sequence
        if not current_sequence or node.val == current_sequence[-1] + 1:
            current_sequence.append(node.val)
        else:
            current_sequence = [node.val]

        longest_sequence_length = max(longest_sequence_length, len(current_sequence))

        # Explore the left and right subtrees
        explore_paths(node.left, current_sequence[:])

        explore_paths(node.right, current_sequence[:])

    # Initiate the recursive traversal to find the longest sequence
    explore_paths(root, [])

    return longest_sequence_length

Big(O) Analysis

Time Complexity

Space Complexity

Optimal Solution

Approach

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

Begin at the very top of the tree, the root.
For each node, check if its value is exactly one more than its parent's value.
If it is, we're continuing a consecutive sequence, so we increase the length of the current sequence by one.
If it's not, we're starting a new sequence, so we reset the sequence length back to one.
As we travel through the tree, keep track of the longest consecutive sequence we've found so far.
Continue this process for every node in the tree.
The final longest length we tracked is the answer.

Code Implementation

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

def longest_consecutive(root):
    longest_sequence = 0

    def depth_first_search(node, parent_value, current_length):
        nonlocal longest_sequence

        if not node:
            return

        # Determine if current node continues sequence.
        if parent_value + 1 == node.value:
            current_length += 1
        else:
            # Reset sequence as it's not consecutive.
            current_length = 1

        # Update the longest sequence found so far.
        longest_sequence = max(longest_sequence, current_length)

        depth_first_search(node.left, node.value, current_length)

        # Explore the right subtree.
        depth_first_search(node.right, node.value, current_length)

    # Initiate the search at the root.
    depth_first_search(root, float('-inf'), 0)

    return longest_sequence

Big(O) Analysis

Time Complexity

Space Complexity

Edge Cases

Case	How to Handle
Null root node	Return 0 immediately as an empty tree has no consecutive sequence.
Single node tree	Return 1 as a single node is a sequence of length 1.
Tree with all identical values	The longest consecutive sequence will be of length 1 because no consecutive numbers exist.
Left-skewed tree	The algorithm should correctly traverse and identify the longest consecutive sequence, possibly with increased stack depth if recursion is used.
Right-skewed tree	The algorithm should correctly traverse and identify the longest consecutive sequence, possibly with increased stack depth if recursion is used.
Very large tree (potential stack overflow with recursion)	Consider iterative approaches using a stack or queue to avoid stack overflow errors with deep trees.
Integer overflow if node values are extremely large	While unlikely given problem constraints, consider using larger integer types if node values could approach maximum integer values.
Tree with negative values that can form consecutive sequence	The algorithm should correctly handle negative values when checking for consecutive sequences by comparing to 'node.val + 1'.