Number Of Nodes With Value One - Leetcode Solution

Problem Description:

Given the root of a binary tree, count the number of nodes where the value of the node is equal to one.

Solution:

To solve this problem, we can use Depth-First Search (DFS) to traverse through the entire binary tree. As we traverse through the tree, we can maintain a count of all the nodes that have the value of one.

The following steps can be performed to solve this problem:

1. Initialize a variable count to zero.
2. Traverse through the binary tree using DFS.
3. At each node, if the value of the node is one, increment the count variable by one.
4. Recursively visit the left and right subtrees of the node.
5. Once all the nodes have been visited, return the final count variable.

The following is the implementation of the above algorithm:

class Solution:
    def countNodes(self, root: TreeNode) -> int:
        if not root:
            return 0
        
        count = 0
        
        def dfs(node):
            nonlocal count
            
            if node:
                if node.val == 1:
                    count += 1
                dfs(node.left)
                dfs(node.right)
                
        dfs(root)
        return count

In the above implementation, we have used a nested function dfs to perform DFS traversal of the binary tree. The nonlocal keyword is used to access the count variable from within the nested function.

Time Complexity:

The time complexity of this algorithm is O(n), where n is the number of nodes in the binary tree. This is because we visit each node exactly once.

Space Complexity:

The space complexity of this algorithm is O(h), where h is the height of the binary tree. This is because the recursive calls are stored on the call stack and the maximum number of recursive calls at any given time is equal to the height of the binary tree.

1