# Binary Tree Visible Nodes Counting

Hi, today I would like to share with you solution of the code puzzle with binary tree. There are 2 tree examples, t1, and t2, and your job is to find visible nodes that are not smaller than all parents. When you go down the t1 tree, you can find 4 such visible nodes. And for the second tree, 2 nodes are visible. The important thing is that the root node is always visible. The tree is defined with 3 fields x is the node value, l is the left node, and r is the right node. Below you can find my solution for looking for all visible nodes in binary trees in C#. I decided to use an iterator that, by going deeper into the tree, carries a maximal value of parents so far. This way, I could find visible nodes in O(N) complexity. All comments are welcome. I hope you like this puzzle solution.

namespace TreeVisibleNodes
{
using System;
using System.Collections.Generic;
class Tree
{
public int x;
public Tree l;
public Tree r;
}
class TreeVisibleSolution
{
#region Tests
static void Main(string[] args)
{
var t0 = default(Tree);
var t1 = new Tree
{
x = 5,
l = new Tree
{
x = 3,
l = new Tree {x = 20},
r = new Tree {x = 21}
},
r = new Tree
{
x = 10,
r = new Tree {x = 1}
}
};
var t2 = new Tree
{
x = 8,
l = new Tree
{
x = 2,
l = new Tree {x = 8},
r = new Tree {x = 7}
},
r = new Tree {x = 3}
};
var testEngine = new Func<string, Tree, int, string>
(
(name, tree, expexted) =>
{
var count = Solution(tree);
return string.Format("Solution({0}) equals {1,2} {2}",
name, count, count == expexted ? "PASS" : "FAIL");
}
);
Console.WriteLine(testEngine("t0", t0, -1));
Console.WriteLine(testEngine("t1", t1,  4));
Console.WriteLine(testEngine("t2", t2,  2));
}
#endregion Tests
#region Solution
private static int Solution(Tree T)
{
if (T == null)
{
return -1;
}
var count = 0;
var stack = new Stack<Tuple<int, Tree>>();
stack.Push(new Tuple<int, Tree>(T.x, T));
while (stack.Count > 0)
{
var n = stack.Pop();
if (n.Item1 <= n.Item2.x)
{
++count;
}
var max = Math.Max(n.Item1, n.Item2.x);
if (n.Item2.l != null)
{
stack.Push(new Tuple<int, Tree>(max, n.Item2.l));
}
if (n.Item2.r != null)
{
stack.Push(new Tuple<int, Tree>(max, n.Item2.r));
}
}
return count;
}
#endregion Solution
}
}

P ;).

This site uses Akismet to reduce spam. Learn how your comment data is processed.