Visible Tree Node

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

Try it yourself

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.

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