LeetCode 1448. Count Good Nodes in Binary Tree (javascript solution) | Microsoft question

#algorithms #javascript

Description:

Given a binary tree root, a node X in the tree is named good if in the path from root to X there are no nodes with a value greater than X.

Return the number of good nodes in the binary tree.

Solution:

Time Complexity : O(n)
Space Complexity: O(height of the tree)

// DFS solution
var goodNodes = function(root, max = root.val) {
    let output = 0
    // Only add to output if we meet the condition
    if(root.val >= max) output++
    // Increase the max if we encounter a val greater than max
    max = Math.max(Math.max(root.val, max))
    // Traverse the tree to compare more nodes
    if(root.left) output += goodNodes(root.left, max)
    if(root.right) output += goodNodes(root.right, max)

    return output   
};