easyTreesPattern: DFS
Count Nodes in Subtree Solution
Problem Statement
Given the root of a binary tree, return the number of nodes in the subtree rooted at a given node. A subtree of a node `p` is `p` plus every node that is a descendant of `p`.
Examples
Example 1:
Input:{"tree":{"val":1,"left":{"val":2,"left":null,"right":null},"right":{"val":3,"left":null,"right":null}},"targetNodeVal":1}
Output:3
Explanation: The subtree rooted at node with value 1 includes nodes 1, 2, and 3. The total count is 3.
Example 2:
Input:{"tree":{"val":1,"left":{"val":2,"left":{"val":4,"left":null,"right":null},"right":{"val":5,"left":null,"right":null}},"right":{"val":3,"left":null,"right":null}},"targetNodeVal":2}
Output:3
Explanation: The subtree rooted at node with value 2 includes nodes 2, 4, and 5. The total count is 3.
Example 3:
Input:{"tree":{"val":1,"left":null,"right":null},"targetNodeVal":1}
Output:1
Explanation: The subtree rooted at node with value 1 includes only node 1 itself. The total count is 1.
Constraints
- The number of nodes in the tree is in the range [0, 1000].
- Node values are unique and in the range [-1000, 1000].
- The target node value exists in the tree.
- The tree can be empty.
Time: O(N) Space: O(N)
Perform a single Depth First Search (DFS) traversal from the root of the tree. During the traversal, for each node, recursively calculate the size of its left and right subtrees. The size of the current node's subtree is 1 plus the sum of the sizes of its left and right children's subtrees. Store these subtree sizes, perhaps in a map where keys are node values and values are subtree sizes. After the DFS completes, retrieve the size for the target node's value.
Run, Test & Submit Code
Ready to practice this challenge? Launch our interactive compilation environment with compiler validation.
Solve on Interactive WorkspaceTested Solutions
class TreeNode:
def __init__(self, val=0, left=None, right=None):
self.val = val
self.left = left
self.right = right
def count_nodes_in_subtree(root: TreeNode, target_node_val: int) -> int:
target_node = None
def find_target_node(node):
nonlocal target_node
if not node:
return
if node.val == target_node_val:
target_node = node
return
find_target_node(node.left)
find_target_node(node.right)
find_target_node(root)
if not target_node:
return 0
def count_nodes(node):
if not node:
return 0
return 1 + count_nodes(node.left) + count_nodes(node.right)
return count_nodes(target_node)