2. Count Visible Nodes in Binary Tree[Microsoft]

Previous Question: All Nodes Distance K in Binary Tree[Microsoft]

2. Count Visible Nodes in Binary Tree[Microsoft]

Next Question: 3. Majority Element[Amazon]

In a binary tree, if in the path from root to the node A, there is no node with greater value than A’s, this node A is visible. We need to count the number of visible nodes in a binary tree.

To solve this problem, developers need to understand few concepts:

How to Approach this problem?

  • Recursive solution
  • Iterative solution

We will see the iterative solution in this article, as making it into recursion will be easy once iterative solution is clear.

While traversing the tree, we need to keep the track of the maximum value of the node that we have seen so far. If the current node is greater or equal to the max value, then increment the count of the visible node and update the max value with the current node value.

  1. Assume you have given a tree node

2. Create a method with responsibility to iterate in DFS and keep max value in stack for DFS.

3. Find Visible nodes

4. Testing code

Thanks for reading this article, keep learning & growing.

Github: https://github.com/charlieInDen/InterviewQuestions-Swift/