That is not the way I read the problem definition. It says “a node “visible” when no node on the root-to-itself path (inclusive) has a greater value”. That means it would still be “visible” even if it was EQUAL to the maximum node on the root-to-itself path because there would still be no value on that path that has a GREATER value.
Structured Programming approach in JS:
function visibleTreeNode(root, prevHighest = -Infinity) {
let count = 0;
if (root) {
let highest = prevHighest;
if (root.val >= prevHighest) {
count++;
highest = root.val;
}
for (const dir of ["left", "right"]) {
count += visibleTreeNode(root[dir], highest);
}
}
return count;
}
And then it gets added to the total again after it comes out of the function call. 
def visible_tree_node(root: Node) → int:
# WRITE YOUR BRILLIANT CODE HERE
def count_visible(head,cur_max):
if head==None:
return 0
if head.val>=cur_max:
return 1+count_visible(head.left,head.val)+count_visible(head.right,head.val)
else:
return count_visible(head.left,cur_max)+count_visible(head.right,cur_max)
return count_visible(root,float('-inf'))
My solution in JS:
function visibleTreeNode(root) {
// WRITE YOUR BRILLIANT CODE HERE
if(!root) return 0;
return dfs(root, root.val);
}
function dfs(node, max) {
if(!node) return 0;
if(node && node.val >= max) {
return 1 + dfs(node.left, node.val) + dfs(node.right, node.val);
} else {
return dfs(node.left, max) + dfs(node.right, max);
}
}
int dfs(Node* parent, int root_val) {
if(parent == nullptr)
return 0;
return (root_val <= parent->val) ? (dfs(parent->left, parent->val) + dfs(parent->right, parent->val)) + 1 : dfs(parent->left, root_val) + dfs(parent->right, root_val);
}
int visible_tree_node(Node* root) {
return dfs(root, root->val);
}
After implementing the tree visualization in the test cases, for same node value, now it is showing as loop (which can’t be possible in tree). Example:
Problem: Visible Tree Node | Number of Visible Nodes
Test Case #5
thanks, it’s fixed. there was an issue with the graph component input where two nodes with same value were considered the same.
I think you need to change the question :
In a binary tree, we define a node “visible” when no node on the root-to-itself path (inclusive) has a greater value
Here says a greater value
but test cases are specting greater or equal value.
Here is my answer in Java :
static int visibleNodes=0;
public static int visibleTreeNode(Node<Integer> root) {
// WRITE YOUR BRILLIANT CODE HERE
if(root==null)
{
return 0;
}
visibleNodes=0;
checkVisibleNodes(root,Integer.MIN_VALUE);
return visibleNodes;
}
private static void checkVisibleNodes(Node<Integer> root, int max) {
if(root==null)
{
return;
}
if(root.val>max)
{
visibleNodes=visibleNodes+1;
max=root.val;
}
checkVisibleNodes(root.left,max);
checkVisibleNodes(root.right,max);
}
I tried to use the global variable approach in Python, but running into some weird error with scoping?
def visible_tree_node(root: Node) -> int:
count = 0
def dfs(root, max_so_far):
if root is None:
return 0
if root.val >= max_so_far:
count += 1
max_so_far = root.val
dfs(root.left, max_so_far)
dfs(root.right, max_so_far)
dfs(root, -float('inf'))
return count
The error is at
count = count + 1
UnboundLocalError: local variable 'count' referenced before assignment
If I understand scoping correctly, the nested function dfs should be able to access the variable count. If anyone had luck trying this in Python and have insight to shed, please
update: apparently using nonlocal count solved the issue… that solution I posted is still wrong however
I’m guessing the scoping thing is something new with Python3, unless I’ve been living under a rock
update #2: oh wait, sorry guys. This is the working solution using global variable in Python. My last attempt didn’t work simply due to indentation error.
def visible_tree_node(root: Node) -> int:
count = 0
def dfs(root, max_so_far):
if root is None:
return 0
if root.val >= max_so_far:
nonlocal count
count += 1
max_so_far = root.val
dfs(root.left, max_so_far)
dfs(root.right, max_so_far)
dfs(root, -float('inf'))
return count
for primitive variables you need nonlocal. if you had a list it’d work as you’d expect. a common workaround with problems that wraps around a Solution class like leetcode is to make it part of the class like self.count. otherwise making it part of the function signature is also fine
Not sure if formatting is kept for easy read, nice and simple in C#:
public static int VisibleTreeNode(Node root)
{
return CountVisible(root,Int32.MinValue);
}
private static int CountVisible(Node<int> node, int max)
{
if(node == null) return 0;
if(max < node.value) max = node.value;
return node.value >= max ? 1 + CountVisible(node.left, max) + CountVisible(node.right, max):
CountVisible(node.left, max) + CountVisible(node.right, max);
}
yeah… I thought it was strictly increasing as well… But test case 4, 5 were failing… so, after looking at it, It was clear that is it node value >= max
We could simplify the code a little bit by using Math.max just once.
public static int dfs(Node<Integer> root, int maxSoFar) {
if (root == null) {
return 0;
}
int total = 0;
if (root.val >= maxSoFar) {
total++;
maxSoFar = Math.max(maxSoFar, root.val);
}
// maxSoFar of the child node is the larger value of previous max and current node val
total += dfs(root.left, maxSoFar);
total += dfs(root.right, maxSoFar);
return total;
}
can be just
maxSoFar = root.val
because if statement already confirms that the root.val is greater (or equal).
“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)”
I get that O(n + n - 1) = O(2n - 1).
But what I don’t get is what does it mean to traverse an edge? Isn’t that the same as traversing a node? What would be the cost of traversing an edge. I get that the cost of traversing a node would be whatever operations are performed inside that node. Please explain.
btw Submitting questions on pages gives unknow error 1.
As of today there are still conflicting definitions of visible. At the very top of the page:
In a binary tree, we define a node “visible” when no node on the root-to-itself path (inclusive) has a greater value.
And later on
The definition for a “visible” node is its value is greater than any other node’s value on the root-to-itself path.
The latter is required to pass the tests.
If this helps anyone, here is how I structured the recursive code in python. Alternative way to code the recursive calls, but similar to the official answer (just more implicit).
def visible_tree_node(root: Node) -> int:
def dfs(node, max_num):
if not node:
return 0
elif node.val >= max_num:
return 1 + dfs(node.left, node.val) + dfs(node.right, node.val)
else:
left = dfs(node.left, max_num)
right = dfs(node.right, max_num)
return left + right
return dfs(root, float('-inf'))