# Visible Tree Node | Number of Visible Nodes

Prereq: DFS on Tree

In a binary tree, a node is considered "visible" if no node on the root-to-itself path has a greater value. The root is always "visible" since there are no other nodes between the root and itself. Given a binary tree, count the number of "visible" nodes.

Input: Output: `3`

## Explanation

We can DFS on the tree and keep track of the max value we have seen as we go.

### 1. Decide on the return value

The problem asks for the total number of visible nodes, so we return the total number of visible nodes for the current subtree after we visit a node.

### 2. Identify states

The definition for a "visible" node is its value is greater than any other node's value on the root-to-itself path. To determine whether the current node is visible or not, we need to know the max value from the root to it. We can carry this as a state as we traverse down the tree.

Having decided on the state and return value we can now write the DFS.

Time Complexity: `O(n)`

There are `n` nodes and `n - 1` edges in a tree so if we traverse each once then the total traversal is `O(2n - 1)` which is `O(n)`.

 `Expand 4 lines ...` `5` `5` `` self.right = right`` `6` `6` `7` `7` ``def visible_tree_node(root: Node) -> int:`` `8` `-` `` # WRITE YOUR BRILLIANT CODE HERE`` `8` `+` `` def dfs(root, max_sofar):`` `9` `-` `` return 0`` `9` `+` `` if not root:`` `10` `+` `` return 0`` `11` `+` `` total = 0`` `12` `+` `` if root.val >= max_sofar:`` `13` `+` `` total += 1`` `14` `+` `15` `+` `` total += dfs(root.left, max(max_sofar, root.val)) # max_sofar for child node is the larger of previous max and current node val`` `16` `+` `` total += dfs(root.right, max(max_sofar, root.val))`` `17` `+` `18` `+` `` return total`` `19` `+` `20` `+` `` # start max_sofar with smallest number possible so any value root has is smaller than it`` `21` `+` `` return dfs(root, -float('inf'))`` `22` `+` `10` `23` ``def build_tree(nodes, f):`` `11` `24` `` val = next(nodes)`` `12` `25` `` if val == 'x': return None`` `13` `26` `` left = build_tree(nodes, f)`` `14` `27` `` right = build_tree(nodes, f)`` `Expand 6 lines ...`