🌲 Finding the Longest Aligned Chain in a Binary Tree

The Challenge

Given a binary tree, we say a node is aligned if its value is the same as its depth (where the root is at depth 0). Our goal is to return the length of the longest descendant chain of aligned nodes.

Note: The chain must follow a parent-to-child path, but it does not need to start at the root.

---

Thought Process

To find the longest chain, we need to traverse the tree while tracking our current depth. A Bottom-Up Depth First Search (DFS) works best here:

1. State Tracking: Pass the current depth down as we move through the tree.
2. Recursive Step: For any node, the longest aligned chain starting at that node depends on the results of its left and right children.
3. The Logic:
4. If node.value == depth, this node is aligned. Its chain length is 1 + max(left_child_chain, right_child_chain).

5. If node.value != depth, the chain breaks. We return 0 to the parent, but we must have already recorded the maximum found so far elsewhere.

6. Global Max: Use a member variable to track the maximum chain length encountered during the entire traversal.

Example:
Input Array: [7, 1, 3, 2, 8, 2, None, 4, 3, None, None, 3, 3]

• Depth 1: Node(1) is aligned.
• Depth 2: Node(2) is aligned.
• Depth 3: Node(3) is aligned.
• Result: 3 (Chain: 1 → 2 → 3)

---

Final Solution

from typing import Optional, List
from collections import deque

class TreeNode:
    def __init__(self, value: int):
        self.value = value
        self.left: Optional["TreeNode"] = None
        self.right: Optional["TreeNode"] = None

class Solution:
    def __init__(self):
        self.res = 0

    def alignedChained(self, root: Optional[TreeNode]) -> int:
        def dfs(node: Optional[TreeNode], depth: int) -> int:
            if not node:
                return 0

            # Post-order traversal: Get values from children first
            left = dfs(node.left, depth + 1)
            right = dfs(node.right, depth + 1)

            if node.value == depth:
                # Node matches depth, extend the chain
                current_chain = 1 + max(left, right)
                self.res = max(self.res, current_chain)
                return current_chain

            # Chain breaks here
            return 0

        dfs(root, 0)
        return self.res

---

Key Takeaways

• In tree problems, always identify if you need information from parents (Top-down) or children (Bottom-up). Here, we needed both (depth from parent, chain length from children).
• The "chain" logic is very similar to the "Longest Path" or "Diameter" problems on LeetCode.

---

Related Problems

• Binary Tree Maximum Path Sum
• Longest Univalue Path
• Diameter of Binary Tree

Tags

#python #algorithms #trees #dfs #recursion