Count Good Nodes in Binary Tree
Count Good Nodes in Binary Tree is a Medium Data Structures and Algorithms interview problem you can solve, run and submit on Thita.ai. It belongs to the Tree Traversal Patterns (DFS & BFS) pattern, in the Recursive Preorder Traversal subpattern.
Problem statement
Implement goodNodes to inspect the binary tree given by root. A node is called good when its value is greater than or equal to every value on the path from the root to that node, including the node itself and the root. The root is therefore good whenever the tree is non-empty.
Return the total number of good nodes in root. A missing child does not represent a node, and an empty tree has no good nodes.
Example 1:
Input: root = [6,2,9,null,4,7,11] Output: 3 Explanation: The root 6 is good, as are 9 and 11. The other nodes each have an earlier, larger value on their root-to-node path.
Example 2:
Input: root = [5,8,3,7,null,null,4] Output: 2 Explanation: The root 5 and node 8 are good. Node 7 is below 8, while nodes 3 and 4 are below the earlier value 5, so they are not good.
Example 3:
Input: root = [] Output: 0 Explanation: The tree is empty, so there are no nodes to count.
Constraints:
- 0 <= number of nodes in root <= 10^5 - -10^4 <= node value <= 10^4 - Each node has at most one left child and one right child - root represents a valid binary tree in level-order form - The tree contains no cycles
Topics and companies
Topics: Binary Tree, Depth-First Search, Tree, Recursion.
How to practise Count Good Nodes in Binary Tree on Thita.ai
Starter code is provided in C#, C++, Go, Java, JavaScript and Python. Your solution runs against 5 test cases for this problem, with the AI coach available for a hint when you are stuck rather than a finished answer. The reference solution runs in O(n), where n is the number of nodes in the tree. time and O(h) auxiliary space, where h is the tree height; O(n) in the worst case. space.
Open Count Good Nodes in Binary Tree in the code editor, or read the Count Good Nodes in Binary Tree editorial for a worked solution with its approach and complexity analysis.
Where Count Good Nodes in Binary Tree sits in the DSA pattern sheet
- Tree Traversal Patterns (DFS & BFS) pattern guide
- Recursive Preorder Traversal subpattern
- The full DSA patterns sheet
- All coding practice problems
Problems related to Count Good Nodes in Binary Tree
Other problems that use the same Recursive Preorder Traversal and Tree Traversal Patterns (DFS & BFS) techniques:
- Binary Tree Paths — Easy, same subpattern
- Binary Tree Preorder Traversal — Easy, same subpattern
- Construct Binary Tree from Preorder and Inorder Traversal — Medium, same subpattern
- Construct Quad Tree — Medium, same subpattern
- Flatten Binary Tree to Linked List — Medium, same subpattern
- Insert into a Binary Search Tree — Medium, same subpattern