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.


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 :frowning:

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) {
        // 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?

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


8 3


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:
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:
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