Count Good Nodes in Binary Tree

Photo by Alessio Zaccaria on Unsplash

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.

Example 1:

Input: root = [3,1,4,3,null,1,5]
Output: 4
Explanation: Nodes in blue are good.
Root Node (3) is always a good node.
Node 4 -> (3,4) is the maximum value in the path starting from the root.
Node 5 -> (3,4,5) is the maximum value in the path
Node 3 -> (3,1,3) is the maximum value in the path.

Example 2:

Input: root = [3,3,null,4,2]
Output: 3
Explanation: Node 2 -> (3, 3, 2) is not good, because "3" is higher than it.

Example 3:

Input: root = [1]
Output: 1
Explanation: Root is considered as good.

Constraints:

  • The number of nodes in the binary tree is in the range [1, 10^5].
  • Each node’s value is between [-10^4, 10^4].

Solution:

We can solve this problem using recursion which is simple and less no of line of codes, another using simple BFS where we will be processing each node by level order.

Complexity:

Run time: O(N) as we traverse the entire tree once.

Space: O(h), where h is height of the tree.

--

--

--

Full Stack Programmer, love to solve problem’s during free time.

Love podcasts or audiobooks? Learn on the go with our new app.

Recommended from Medium

10 Things You Should Know for Your First Developer Job

Globally Distributed Cross Functional Squads Are A Good Thing

A Developers Guide to Conversion (Link Click) Tracking with Google Tag Manger, Google Adwords, and…

Tutorial: Saving high scores in your game with castle.storage

Ballerina Packaging Architecture and Understanding the Client Connectors

Pivotal Tracker, a very interesting and helpful project management tool

Evangelicalism in America is nearing extinction due to the movement’s devotion to politics at the…

Python: Getting Started with Pandas

Get the Medium app

A button that says 'Download on the App Store', and if clicked it will lead you to the iOS App store
A button that says 'Get it on, Google Play', and if clicked it will lead you to the Google Play store
Jaydeep

Jaydeep

Full Stack Programmer, love to solve problem’s during free time.

More from Medium

Centralization or Decentralization

Space Complexity

JVM Continues … Go deep inside !!

A Simple Framework for Generating Machine Learning Project Ideas to Start Building Your Side…