Learning Journal

2/9/2024

Count Nodes Equal to Average of Subtree

/**
 * Definition for a binary tree node.
 * class TreeNode {
 *     val: number
 *     left: TreeNode | null
 *     right: TreeNode | null
 *     constructor(val?: number, left?: TreeNode | null, right?: TreeNode | null) {
 *         this.val = (val===undefined ? 0 : val)
 *         this.left = (left===undefined ? null : left)
 *         this.right = (right===undefined ? null : right)
 *     }
 * }
 */

function averageOfSubtree(root: TreeNode | null): number {
    if(!root) return 0;

    const numL = averageOfSubtree(root.left);
    const numR = averageOfSubtree(root.right);
    
    const [total, numNodes] = inspect(root);

    if(Math.floor(total/numNodes) === root.val)
        return numL + numR + 1;

    return numL + numR;

};

function inspect(node:TreeNode | null): number[] {
    if(!node) return [0,0];

    let total = node.val, numNodes = 1;

    if(node.left){
        const [totalL, numNodesL] = inspect(node.left);
        total += totalL;
        numNodes += numNodesL;
    }

    if(node.right){
        const [totalR, numNodesR] = inspect(node.right);
        total += totalR;
        numNodes += numNodesR;
    }

    return [total, numNodes];
}/**
 * Definition for a binary tree node.
 * class TreeNode {
 *     val: number
 *     left: TreeNode | null
 *     right: TreeNode | null
 *     constructor(val?: number, left?: TreeNode | null, right?: TreeNode | null) {
 *         this.val = (val===undefined ? 0 : val)
 *         this.left = (left===undefined ? null : left)
 *         this.right = (right===undefined ? null : right)
 *     }
 * }
 */

function averageOfSubtree(root: TreeNode | null): number {
    if(!root) return 0;

    const numL = averageOfSubtree(root.left);
    const numR = averageOfSubtree(root.right);
    
    const [total, numNodes] = inspect(root);

    if(Math.floor(total/numNodes) === root.val)
        return numL + numR + 1;

    return numL + numR;

};

function inspect(node:TreeNode | null): number[] {
    if(!node) return [0,0];

    let total = node.val, numNodes = 1;

    if(node.left){
        const [totalL, numNodesL] = inspect(node.left);
        total += totalL;
        numNodes += numNodesL;
    }

    if(node.right){
        const [totalR, numNodesR] = inspect(node.right);
        total += totalR;
        numNodes += numNodesR;
    }

    return [total, numNodes];
}

THE PROBLEM

This is my solution to this problem at first attempt.

The algorithm starts with the root, gets the number of valid subtrees in the left and right subtrees, and then checks if the root is a valid subtree. If it is, return the number of valid subtrees in the left and the right subtree plus 1 (for the root).

This algorithm works because when it reaches null, it will return 0. So, because a leaf node has both of its children null, they all return 0. The function inspect will return the total as the value of that node, and numNodes is 1 (because it has no left or right child). Thus, the main function will return 1 if it is called on a leaf node. If it is called on a non-leaf node, it will return the number of its leaves plus 1 or not, depending on whether or not it's a valid subtree.

Revised by ChatGPT

This is my solution to the problem as described in Count Nodes Equal to Average of Subtree.

The algorithm begins at the root node determining the count of valid subtrees within both the left and right subtrees. It then evaluates whether the root itself constitutes a valid subtree. If the root qualifies, the algorithm returns the sum of valid subtrees from both the left and the right, incremented by 1 to account for the root.

The effectiveness of this algorithm is attributed to its behavior when encountering a null node, at which point it returns 0. Consequently, when a leaf node is reached - characterized by its left and right children being null - the function yields 0 for both. The inspect function, in this context, returns the leaf node's value as the total, and the number of nodes as 1 (given the absence of child nodes). Therefore, if the function is invoked on a leaf node, it will return 1. When executed on non-leaf node, the function returns the sum of its valid leaf nodes, increased by 1 if the node itself represents a valid subtree.