Jobs

Interviews

Discussions

Binary Tree Longest Consecutive Sequence II

Medium

Asked by:

11 views

Topics:

TreesRecursion

Given the root of a binary tree, return the length of the longest consecutive sequence path.

The path refers to any sequence of nodes from some starting node to any node in the tree along the parent-child connections. The longest consecutive path needs to be from parent to child (cannot go upwards).

Example 1:

Input: root = [1,null,3,2,4,null,null,null,5]
Output: 3
Explanation: Longest consecutive sequence path is 3-4-5, so return 3.

Example 2:

Input: root = [2,null,3,2,null,1]
Output: 2
Explanation: Longest consecutive sequence path is 2-3, not 3-2-1, so return 2.

Constraints:

The number of nodes in the tree is in the range [1, 3 * 10⁴].
-3 * 10⁴ <= Node.val <= 3 * 10⁴

Try coding it in LeetCode

Binary Tree Longest Consecutive Sequence II

Medium

Asked by:

11 views

Topics:

TreesRecursion

Given the root of a binary tree, return the length of the longest consecutive sequence path.

Example 1:

Input: root = [1,null,3,2,4,null,null,null,5]
Output: 3
Explanation: Longest consecutive sequence path is 3-4-5, so return 3.

Example 2:

Input: root = [2,null,3,2,null,1]
Output: 2
Explanation: Longest consecutive sequence path is 2-3, not 3-2-1, so return 2.

Constraints:

The number of nodes in the tree is in the range [1, 3 * 10⁴].
-3 * 10⁴ <= Node.val <= 3 * 10⁴

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:

Can the values in the binary tree be negative, zero, or only positive integers?
If there are multiple longest consecutive sequences of the same length, should I return just one of them, or is there a specific criteria for choosing which one?
What should be returned if the tree is empty, or if there is no consecutive sequence of length greater than 1?
Are consecutive sequences required to be strictly increasing/decreasing, or can they be non-decreasing/non-increasing?
Is the binary tree guaranteed to be a binary search tree, or is it just a regular binary tree?

Brute Force Solution

Approach

The brute force method for this problem involves exploring every single path within the tree. We essentially check every possible combination of connected nodes to find the longest sequence where the values either increase or decrease by one.

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

Start at the very top of the tree.
From that top node, look at every single path downwards to the leaves.
For each of these paths, check if the node values form a sequence where each value is one greater or one smaller than the previous node.
Remember the length of each increasing or decreasing sequence you find.
Once you have checked all possible paths downwards starting from the top, repeat the entire process, but this time start from each of the other nodes in the tree, one by one.
Again, from each of these starting nodes, look at every possible path downwards.
For each of these paths, check if the node values form an increasing or decreasing sequence.
Compare the lengths of all increasing or decreasing sequences you found from all starting nodes.
The longest sequence you found is the answer.

Code Implementation

def longest_consecutive_sequence_ii_brute_force(root):
    maximum_length = 0

    def get_all_paths(node):
        if not node:
            return []

        if not node.left and not node.right:
            return [[node.val]]

        paths = []
        for path in get_all_paths(node.left):
            paths.append([node.val] + path)
        for path in get_all_paths(node.right):
            paths.append([node.val] + path)
        return paths

    def find_longest_consecutive(paths):
        nonlocal maximum_length
        for path in paths:
            increasing_length = 1
            decreasing_length = 1

            # Determine the longest increasing sequence
            for i in range(len(path) - 1):
                if path[i+1] == path[i] + 1:
                    increasing_length += 1
                else:
                    maximum_length = max(maximum_length, increasing_length)
                    increasing_length = 1

            # Determine the longest decreasing sequence
            for i in range(len(path) - 1):
                if path[i+1] == path[i] - 1:
                    decreasing_length += 1
                else:
                    maximum_length = max(maximum_length, decreasing_length)
                    decreasing_length = 1

            maximum_length = max(maximum_length, increasing_length, decreasing_length)

    def traverse_tree(node):
        nonlocal maximum_length
        if not node:
            return

        all_paths = get_all_paths(node)
        find_longest_consecutive(all_paths)

        traverse_tree(node.left)

        # Recursively call for the right sub-tree
        traverse_tree(node.right)

    # Initiates the traversal from the root
    traverse_tree(root)

    return maximum_length

Big(O) Analysis

Time Complexity

O(n²) – The described brute force approach iterates through each node in the binary tree as a starting point, resulting in n iterations where n is the number of nodes. For each starting node, the algorithm explores all possible paths downwards. In the worst-case scenario, each node can be the start of a path that visits a significant portion of the tree, leading to another factor related to n. Therefore, the total operations can be approximated as n * n, which simplifies to O(n²).

Space Complexity

O(N) – The brute force approach explores all paths from each node in the binary tree using recursion. In the worst-case scenario (e.g., a skewed tree), the recursion depth can reach N, where N is the number of nodes in the tree. Each recursive call adds a new frame to the call stack, consuming memory. Therefore, the auxiliary space complexity is determined by the maximum depth of the recursion, which is O(N).

Optimal Solution

Approach

This problem asks us to find the longest sequence of numbers in a binary tree where the numbers increase or decrease by one at each step. The optimal approach involves exploring each path in the tree and keeping track of both increasing and decreasing sequences from each node.

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

Think about starting at the very top of the tree and traveling down each branch.
As you go down, at each point consider two things: Can you extend a sequence where numbers increase by one? Can you extend a sequence where numbers decrease by one?
Keep track of the length of the longest increasing and decreasing sequences you can form starting at each point in the tree.
When you reach a point in the tree, compare its value to its parent. If it's one bigger, you've extended an increasing sequence. If it's one smaller, you've extended a decreasing sequence.
Pass the information about the longest increasing and decreasing sequences back up the tree after exploring each branch.
At each node, the longest consecutive sequence will be the maximum of its own increasing and decreasing sequences, and the longest sequences found in its subtrees.
Keep a global record of the longest sequence found anywhere in the tree and update it whenever you find a longer one.
After exploring the whole tree, the global record will hold the length of the longest consecutive sequence.

Code Implementation

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

class Solution:
    def longestConsecutive(self, root):
        self.longest_sequence = 0
        self.longestConsecutiveHelper(root)
        return self.longest_sequence

    def longestConsecutiveHelper(self, root):
        if not root:
            return 0, 0

        increasing_length = 1
        decreasing_length = 1

        left_increasing_length, left_decreasing_length = self.longestConsecutiveHelper(root.left)
        right_increasing_length, right_decreasing_length = self.longestConsecutiveHelper(root.right)

        # Check left child for consecutive sequence extension
        if root.left:
            if root.value == root.left.value + 1:
                decreasing_length = max(decreasing_length, left_decreasing_length + 1)
            elif root.value == root.left.value - 1:
                increasing_length = max(increasing_length, left_increasing_length + 1)

        # Check right child for consecutive sequence extension
        if root.right:
            if root.value == root.right.value + 1:
                decreasing_length = max(decreasing_length, right_decreasing_length + 1)
            elif root.value == root.right.value - 1:
                increasing_length = max(increasing_length, right_increasing_length + 1)

        current_longest = increasing_length + decreasing_length - 1

        # Update the global longest sequence
        self.longest_sequence = max(self.longest_sequence, current_longest)

        return increasing_length, decreasing_length

Big(O) Analysis

Time Complexity

O(n) – The algorithm performs a depth-first traversal of the binary tree. Each node in the tree is visited exactly once. At each node, a constant amount of work is done to compare the node's value to its children and update the increasing/decreasing sequence lengths. Since we visit each of the n nodes in the tree once and perform constant-time operations at each node, the overall time complexity is O(n).

Space Complexity

O(N) – The primary driver of auxiliary space complexity is the recursion stack. In the worst-case scenario, such as a skewed tree, the recursive calls can go as deep as the number of nodes in the tree, N. Each recursive call adds a new frame to the stack, requiring memory to store local variables and the return address. Therefore, the space used by the recursion stack grows linearly with the number of nodes, resulting in O(N) space complexity.

Edge Cases

Case	How to Handle
Null or empty tree	Return 0, as there's no consecutive sequence in an empty tree.
Tree with only one node	Return 1, as a single node is a consecutive sequence of length 1.
Skewed tree (all nodes on one side)	The algorithm should correctly traverse and calculate the longest consecutive sequence regardless of the tree's shape.
Tree with nodes having duplicate values	The recursive approach should handle duplicate values by considering all possible paths, resetting the sequence when non-consecutive values are encountered.
Large tree (deep recursion)	Ensure the solution avoids stack overflow by using iterative approach or optimized recursion with limited depth if necessary.
Consecutive sequence decreases instead of increasing	The algorithm needs to track both increasing and decreasing sequences and choose the larger one.
No consecutive sequence exists	The algorithm should return 1 in this case because single node is considered consecutive sequence of size 1.
Integer overflow if node values are large and sequence is long	Consider using long integers to avoid overflow issues when calculating the length of the sequences.

Null or empty tree

How to Handle:

Return 0, as there's no consecutive sequence in an empty tree.

Tree with only one node

How to Handle:

Return 1, as a single node is a consecutive sequence of length 1.

Skewed tree (all nodes on one side)

How to Handle:

The algorithm should correctly traverse and calculate the longest consecutive sequence regardless of the tree's shape.

Tree with nodes having duplicate values

How to Handle:

The recursive approach should handle duplicate values by considering all possible paths, resetting the sequence when non-consecutive values are encountered.

Large tree (deep recursion)

How to Handle:

Ensure the solution avoids stack overflow by using iterative approach or optimized recursion with limited depth if necessary.

Consecutive sequence decreases instead of increasing

How to Handle:

The algorithm needs to track both increasing and decreasing sequences and choose the larger one.

No consecutive sequence exists

How to Handle:

The algorithm should return 1 in this case because single node is considered consecutive sequence of size 1.

Integer overflow if node values are large and sequence is long

How to Handle:

Consider using long integers to avoid overflow issues when calculating the length of the sequences.

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 values in the binary tree be negative, zero, or only positive integers?
If there are multiple longest consecutive sequences of the same length, should I return just one of them, or is there a specific criteria for choosing which one?
What should be returned if the tree is empty, or if there is no consecutive sequence of length greater than 1?
Are consecutive sequences required to be strictly increasing/decreasing, or can they be non-decreasing/non-increasing?
Is the binary tree guaranteed to be a binary search tree, or is it just a regular binary tree?

Brute Force Solution

Approach

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

Start at the very top of the tree.
From that top node, look at every single path downwards to the leaves.
For each of these paths, check if the node values form a sequence where each value is one greater or one smaller than the previous node.
Remember the length of each increasing or decreasing sequence you find.
Once you have checked all possible paths downwards starting from the top, repeat the entire process, but this time start from each of the other nodes in the tree, one by one.
Again, from each of these starting nodes, look at every possible path downwards.
For each of these paths, check if the node values form an increasing or decreasing sequence.
Compare the lengths of all increasing or decreasing sequences you found from all starting nodes.
The longest sequence you found is the answer.

Code Implementation

def longest_consecutive_sequence_ii_brute_force(root):
    maximum_length = 0

    def get_all_paths(node):
        if not node:
            return []

        if not node.left and not node.right:
            return [[node.val]]

        paths = []
        for path in get_all_paths(node.left):
            paths.append([node.val] + path)
        for path in get_all_paths(node.right):
            paths.append([node.val] + path)
        return paths

    def find_longest_consecutive(paths):
        nonlocal maximum_length
        for path in paths:
            increasing_length = 1
            decreasing_length = 1

            # Determine the longest increasing sequence
            for i in range(len(path) - 1):
                if path[i+1] == path[i] + 1:
                    increasing_length += 1
                else:
                    maximum_length = max(maximum_length, increasing_length)
                    increasing_length = 1

            # Determine the longest decreasing sequence
            for i in range(len(path) - 1):
                if path[i+1] == path[i] - 1:
                    decreasing_length += 1
                else:
                    maximum_length = max(maximum_length, decreasing_length)
                    decreasing_length = 1

            maximum_length = max(maximum_length, increasing_length, decreasing_length)

    def traverse_tree(node):
        nonlocal maximum_length
        if not node:
            return

        all_paths = get_all_paths(node)
        find_longest_consecutive(all_paths)

        traverse_tree(node.left)

        # Recursively call for the right sub-tree
        traverse_tree(node.right)

    # Initiates the traversal from the root
    traverse_tree(root)

    return maximum_length

Big(O) Analysis

Time Complexity

Space Complexity

Optimal Solution

Approach

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

Think about starting at the very top of the tree and traveling down each branch.
As you go down, at each point consider two things: Can you extend a sequence where numbers increase by one? Can you extend a sequence where numbers decrease by one?
Keep track of the length of the longest increasing and decreasing sequences you can form starting at each point in the tree.
When you reach a point in the tree, compare its value to its parent. If it's one bigger, you've extended an increasing sequence. If it's one smaller, you've extended a decreasing sequence.
Pass the information about the longest increasing and decreasing sequences back up the tree after exploring each branch.
At each node, the longest consecutive sequence will be the maximum of its own increasing and decreasing sequences, and the longest sequences found in its subtrees.
Keep a global record of the longest sequence found anywhere in the tree and update it whenever you find a longer one.
After exploring the whole tree, the global record will hold the length of the longest consecutive sequence.

Code Implementation

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

class Solution:
    def longestConsecutive(self, root):
        self.longest_sequence = 0
        self.longestConsecutiveHelper(root)
        return self.longest_sequence

    def longestConsecutiveHelper(self, root):
        if not root:
            return 0, 0

        increasing_length = 1
        decreasing_length = 1

        left_increasing_length, left_decreasing_length = self.longestConsecutiveHelper(root.left)
        right_increasing_length, right_decreasing_length = self.longestConsecutiveHelper(root.right)

        # Check left child for consecutive sequence extension
        if root.left:
            if root.value == root.left.value + 1:
                decreasing_length = max(decreasing_length, left_decreasing_length + 1)
            elif root.value == root.left.value - 1:
                increasing_length = max(increasing_length, left_increasing_length + 1)

        # Check right child for consecutive sequence extension
        if root.right:
            if root.value == root.right.value + 1:
                decreasing_length = max(decreasing_length, right_decreasing_length + 1)
            elif root.value == root.right.value - 1:
                increasing_length = max(increasing_length, right_increasing_length + 1)

        current_longest = increasing_length + decreasing_length - 1

        # Update the global longest sequence
        self.longest_sequence = max(self.longest_sequence, current_longest)

        return increasing_length, decreasing_length

Big(O) Analysis

Time Complexity

Space Complexity

Edge Cases

Case	How to Handle
Null or empty tree	Return 0, as there's no consecutive sequence in an empty tree.
Tree with only one node	Return 1, as a single node is a consecutive sequence of length 1.
Skewed tree (all nodes on one side)	The algorithm should correctly traverse and calculate the longest consecutive sequence regardless of the tree's shape.
Tree with nodes having duplicate values	The recursive approach should handle duplicate values by considering all possible paths, resetting the sequence when non-consecutive values are encountered.
Large tree (deep recursion)	Ensure the solution avoids stack overflow by using iterative approach or optimized recursion with limited depth if necessary.
Consecutive sequence decreases instead of increasing	The algorithm needs to track both increasing and decreasing sequences and choose the larger one.
No consecutive sequence exists	The algorithm should return 1 in this case because single node is considered consecutive sequence of size 1.
Integer overflow if node values are large and sequence is long	Consider using long integers to avoid overflow issues when calculating the length of the sequences.

Null or empty tree

How to Handle:

Return 0, as there's no consecutive sequence in an empty tree.

Tree with only one node

How to Handle:

Return 1, as a single node is a consecutive sequence of length 1.

Skewed tree (all nodes on one side)

How to Handle:

The algorithm should correctly traverse and calculate the longest consecutive sequence regardless of the tree's shape.

Tree with nodes having duplicate values

How to Handle:

The recursive approach should handle duplicate values by considering all possible paths, resetting the sequence when non-consecutive values are encountered.

Large tree (deep recursion)

How to Handle:

Ensure the solution avoids stack overflow by using iterative approach or optimized recursion with limited depth if necessary.

Consecutive sequence decreases instead of increasing

How to Handle:

The algorithm needs to track both increasing and decreasing sequences and choose the larger one.

No consecutive sequence exists

How to Handle:

The algorithm should return 1 in this case because single node is considered consecutive sequence of size 1.

Integer overflow if node values are large and sequence is long

How to Handle:

Consider using long integers to avoid overflow issues when calculating the length of the sequences.