LeetCode 1448. Count Good Nodes in Binary Tree (javascript solution) | Microsoft question
codingpineapple
Posted on April 12, 2021
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
};
π πͺ π
π©
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
sorting Recap the highlight of the sorting algorithms using JavaScript for beginners
October 5, 2024
datastructures DSA with JS: Understanding Custom Array Data Structure in JavaScript - A Step-by-Step Guide
September 29, 2024