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

cod3pineapple

codingpineapple

Posted on April 12, 2021

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

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   
};
Enter fullscreen mode Exit fullscreen mode
πŸ’– πŸ’ͺ πŸ™… 🚩
cod3pineapple
codingpineapple

Posted on April 12, 2021

Join Our Newsletter. No Spam, Only the good stuff.

Sign up to receive the latest update from our blog.

Related