# Visible Tree Node - Depth First Search / DFS on Tree

Visible Node is a node that on a given path from the root to that node there arenâ€™t any values greater than the current node? A little confused with the wording.

2 Likes

So I think if 6 had a right child of value 8, 6 and 8 are both visible according to the solution

Given a node n , if you traverse from root till that node and the max value among the node visited is of n then that node is visible.

Was also confused here. It just means that the current node must have a higher value than each of its ancestors (parent, grandparent, etc.)
At least thatâ€™s the logic I used to get the correct answer.

Say youâ€™re on node 8, and you follow the path up to the root. Notice every node value on that path is no larger than 8. Thats what makes it a visible node.

The comment in the solution reads â€ś// Start maxSoFar with smallest integer value possible so any value root has is smaller than itâ€ť.

Shouldnâ€™t it be â€ś// Start maxSoFar with smallest integer value possible so any value root has is GREATER than itâ€ť

Thank you for pointing out. Weâ€™ve fixed the typo.

function dfs(root, max_sofar = node.val) {â€¦} is also neat, as we donâ€™t need Number.NEGATIVE_INFINITY.

Was doing it with a maxheap but it was clearly overdesign

Leetcode 1448 Count Good Nodes in Binary Tree
for anybody else whose tracking their progress on LC too

Hey mod, I dont think the test case #4, is correct. 5 8 3 x x 8 x x 6 x x should have 3 visible nodes, not 4. Namely, 5 (root), 8 (left child of root, i.e. 8>5), 6 (right child of root, i.e. 6>5), and no other. the 8 in the right child of 8, is not visible since its equal to its root node. And for that I think the solution can be corrected as follows:

``````
public static int visibleTreeNode(Node<Integer> node) {
// WRITE YOUR BRILLIANT CODE HERE
// the root node is always visible, hence +1
return 1 + visibleTreeNode(node, node.val);
}

public static int visibleTreeNode(Node<Integer> node, int max) {
if (node == null) return 0;

int count = 0;
if (node.val > max) count++;

count += visibleTreeNode(node.left, Math.max(max, node.val));
count += visibleTreeNode(node.right, Math.max(max, node.val));
return count;
}

``````

Any thoughts, mod?
Thanks

Yeah I noticed the same, I believe the tree looks like:

``````5
``````

/
8 3
/
8

6

which according to the definition of a visible node being the greatest node value on a root-to-self (inclusive) path, 6 should not be counted as a visible node, and there should only be 3.

Sorry that tree did not show up as I had planned XD

Yes, this answer should be 3 for this test case.
The solution uses if root.val >= max_sofar, but it should be â€ś>â€ť, because the question says â€śhas a greater (>) valueâ€ť.

why does total not get overridden to 0 each time

Total doesnâ€™t get rewritten to 0 each time because each recursive step is an entirely new and independent function call. Every other recursive call will have its own separate â€śtotalâ€ť that will get returned up to our first function.

def visible_tree_node(root: Node) â†’ int:
# WRITE YOUR BRILLIANT CODE HERE
def dfs(root,max_tillNow):
if not root:
return 0

``````    if root.val >= max_tillNow:
return 1 + (dfs(root.left,max(root.val,max_tillNow)) + dfs(root.right,max(root.val,max_tillNow)))

return dfs(root, -float('inf'))
``````

why there is error in my return type. saying unspported operand + nonetype and int

You need another return in dfs

Felt clever:
def visible_tree_node(root: Node) â†’ int:
# WRITE YOUR BRILLIANT CODE HERE
if root == None:
return 0
left = visible_tree_node(root.left)
right = visible_tree_node(root.right)
if root.left and root.val > root.left.val:
left -= 1
if root.right and root.val > root.right.val:
right -= 1
return left + right + 1