Diameter of Binary Tree

Problem

Given the?root?of a binary tree, return?the length of the?diameter?of the tree.

The?diameter?of a binary tree is the?length?of the longest path between any two nodes in a tree. This path may or may not pass through the?root.

The?length?of a path between two nodes is represented by the number of edges between them.

Example 1:

Input: root = [1,2,3,4,5]
Output: 3
Explanation: 3 is the length of the path [4,2,1,3] or [5,2,1,3].

Example 2:

Input: root = [1,2]
Output: 1

Intuition

The task is to find and count the number of "good" nodes in a binary tree. A "good" node is defined as a node in which the value of the node is greater than or equal to the maximum value along the path from the root to that node. The intuition is to perform a depth-first search (DFS) traversal of the binary tree and count the "good" nodes encountered during the traversal.

Approach

Initialization:

Initialize a variable res to store the count of "good" nodes.
Initialize a variable prev to represent the maximum value along the path from the root to the current node.
Start the DFS traversal with the root of the binary tree.
Depth-First Search (DFS):

Implement a recursive DFS function dfs that takes the current node and the maximum value prev encountered so far.
If the value of the current node is greater than or equal to prev, increment the res count and update prev to the value of the current node.
Recursively call dfs on the left and right subtrees of the current node, passing the updated prev value.
Return Result:

Return the final count of "good" nodes stored in the res variable.

Complexity

• Time complexity:

The time complexity is O(n), where n is the number of nodes in the binary tree. Each node is visited exactly once during the traversal.

• Space complexity:

The space complexity is O(h), where h is the height of the binary tree. This is because the maximum depth of the recursion stack is equal to the height of the tree. In the average case, for a balanced binary tree, the height is O(log n), making the space complexity O(log n). However, in the worst case of an unbalanced tree, the height could be O(n), resulting in a space complexity of O(n). The space complexity is dominated by the depth of the recursive call stack.

Code

# Definition for a binary tree node.
# class TreeNode:
#     def __init__(self, val=0, left=None, right=None):
#         self.val = val
#         self.left = left
#         self.right = right
class Solution:
    def goodNodes(self, root: TreeNode) -> int:
        res = [0]
        prev = root

        def dfs(node, prev):
            if not node:
                return

            if node.val >= prev.val:
                res[0] += 1
                prev = node
            
            dfs(node.left, prev)
            dfs(node.right, prev)

        dfs(root, prev)
        return res[0]