Bottom-Up DFS with Recursion
In this method, a bottom-up depth-first search (DFS) is carried out recursively. For every node reached during the traversal, the sum and count of nodes for its left and right subtrees are calculated recursively. Afterward, the sum and count of nodes for the current subtree are determined by adding the sums and counts of its left and right subtrees, alongside the current node. Subsequently, the average of the current subtree is computed, and the maximum average is adjusted accordingly.
Example: The example below shows how to Find the subtree with the maximum average in a binary tree using Bottom-Up DFS with Recursion.
class TreeNode {
constructor(val) {
this.val = val;
this.left = this.right = null;
}
}
const maxAvgSubt = (root) => {
const calSubtreeS = (node) => {
if (!node) return { sum: 0, count: 0 };
const left = calSubtreeS(node.left);
const right = calSubtreeS(node.right);
const sum = left.sum + right.sum + node.val;
const count = left.count + right.count + 1;
return { sum, count };
};
let maxAverage = Number.MIN_SAFE_INTEGER;
const dfs = (node) => {
if (!node) return;
const { sum, count } = calSubtreeS(node);
const average = sum / count;
maxAverage = Math.max(maxAverage, average);
dfs(node.left);
dfs(node.right);
};
dfs(root);
return maxAverage;
};
// Constructing the binary tree
const root2 = new TreeNode(5);
root2.left = new TreeNode(6);
root2.right = new TreeNode(7);
root2.left.left = new TreeNode(3);
root2.left.right = new TreeNode(4);
// Finding the maximum average subtree
const result2 = maxAvgSubt(root2);
console.log("Maximum average subtree:", result2);
Output
Maximum average subtree: 7
Time Complexity: O(n), where n is the number of nodes in the binary tree.
Space Complexity: O(h), where h is the height of the binary tree.
Find the Subtree with the Maximum Average in a Binary Tree using JavaScript
Given a binary tree, our task is to find the subtree with the maximum average in JavaScript. The average of a subtree is defined as the sum of all node values within the subtree divided by the number of nodes it contains.
Example:
Input:
5
/ \
6 7
/ \
3 4
Output: 7
Explanation
Average of values of subtree of node 5 = (5 + 6 + 7+3 +4) / 5 = 5
Average of values of subtree of node 6 = (6+3 +4) / 3 = 4.33
Average of values of subtree of node 7 = 7 / 1 = 7
Average of values of subtree of node 3 = 3 / 1 = 3
Average of values of subtree of node 4 = 4 / 1 = 4
Below are the approaches to finding the subtree with the maximum average in a binary tree using JavaScript:
Table of Content
- Brute Force Approach (DFS for each node)
- Bottom-Up DFS with Recursion
- Optimized Bottom-Up DFS with Recursion
- Iterative Bottom-Up DFS with Stack
- Top-Down DFS with Memoization