Naming

The naming in the specs is awful.

For one thing, the Tree class:

class Tree
{
    public int x;
    public Tree l;
    public Tree r;
}

This class is bad for several reasons:

• It's exposing its private fields;
• Publicly accessible members have cryptic names;
• The names chosen don't follow naming conventions for public members, which is PascalCasing.

The solution method:

• Also has a bad name - method names should start with a verb that says what the method does;
• Takes a T parameter of type Tree; T is typically ok as a name for a type parameter name in a generic class. Parameters should be camelCase, so a better name would have been tree.
• Because of the bad naming, the entire content of the method is barely readable.

Nitpicks

Couple more points:

• Scopes are not explicitly defined. It's always best to include the braces for an if block, even if it's a single line of code.
• The solution could have been encapsulated in its own class, and made non-static.
• Each if is redundantly checking if T.l != null or T.r != null; you could have regrouped the cases where [T.l == null | T.r == null] and arranged the conditionals in such a way that you wouldn't need to check again something you've checked already.

Creational Patterns

I think most of the code in the Main method belongs in a Builder or Factory class whose role is to create a Tree. All this manual setup looks like a missed opportunity at implementing a Builder pattern.

I believe your MainTreeNodeValue is throwing you off a bit. For starters, you only want to set it when you start traversing the tree - ie, you only want to set it once. A case where your code won't work is when the root value is 0. This will cause your if statement to set MainTreeNodeValue to 0, which will cause the if statement to be hit again on a lower level, and your MainTreeNodeValue will eventually be set to some non-zero value, which you don't want because your tree's root value is in fact 0.

Typically, in cases like this, there is a helper function that helps initialize things along with kicking off the recursion. Here's an example:

int MainTreeNodeValue; // This should not be a static variable!
public int solution(Tree T) 
{
    MainTreeNodeValue = T.x;
    return solutionHelper(T); // returns your final 'count'
}

private int solutionHelper(Tree T) // private to hide visibility.
{ 
    // Your code here 
}

Also, your algorithm won't work because it doesn't evaluate all nodes. Regardless of whether the current node is visible or not is not important, you must evaluate both children regardless.

I won't put the answer here, but your solution should have this basic layout:

// (All of this in solutionHelper(Tree t), as seen above)

if (T == null)
{
    // We want to break out of here if T is null, 
    //so we don't call T.x, T.l, or T.r on a null pointer.
    return 0; 
}

int visibility = isVisible(T) ? 1 : 0; // I'll leave it up to you to implement this.

// Always evaluate T.l and T.r!
return visibility + solutionHelper(T.l) + solutionHelper(T.r);

The tricky part is determining if the current node is visible. You will most likely need to maintain a stack or some other data structure, but I'll leave that as an exercise for the reader. You should note, however, that I don't use the MainTreeNodeValue or count anywhere.

Edit 1:

There may be some confusion on what the problem is asking. The problem says:

A node of that tree containing value V is described as visible if the path from the root of the tree to the node does not contain a node with any value exceeding V.

I read that like this: the current node we are looking at has the value V. As in, T.x == V. The node T is visible if the path from the root of the tree to T does not contain a value greater than T.x. Take this tree for example(right sides are ignored for simplicity):

      5
     /
    1
   /
  2
 /
6

I would say that 5 and 6 are visible. 6 is visible because none of the previous nodes exceed its value(including the root node). Take this tree for example, though:

      5
     /
    1
   /
  2
 /
3

Only 5 is visible, because 3 is exceeded by the root node. However, and perhaps most importantly, you're missing this case(which doesn't exist in your problem's setup either):

      5
     /
    10
   /
  20
 /
40

All nodes here are visible nodes. 5 is visible because it's the rood node, 10 is visible because 5 does not exceed it, 20 is visible because neither 5 nor 10 exceed it, and 40 is visible because 5, 10, and 20 don't exceed it.

In the examples given, all of the intermediate values between the root and the visible nodes happen to be less than the root node's value, but that is not a requirement for a node to be visible. A node is visible if and only if all values preceding it - including the root node's - are lower.

Functional problems

You don't run the software using the test data given in the problem definition; so the reader doesn't know whether your solution returns the correct result for those two test cases.

Recursion is the obvious way to solve this problem; however it won't work: because when N is 1,000,000 as specified in the problem description, that much recursion is likely to cause a stack overflow. Therefore you should demonstrate that you know how (e.g. by using local heap-based stack variable) to unroll the recursion: how to iterate all the nodes of a tree without using recursion.

Stylistic problems

Stylistic problems are important too:

• You're writing source code for other programmers to read: not just writing for the compiler
• People (e.g. hiring managers) are IMO likely to judge you and your code based on its appearance as well as on its behaviour

So:

1. The formatting is poor:

   • Too much indentation
   • Too many blank lines

2. Too many global (i.e. static) variables; count and MainTreeNodeValue could be instance data members of a Solution class, or passed as parameters into the static solution method.

3. Inconsistent capitalization of variable names: sometimes they're lower-case (e.g. count) and sometimes upper-case (e.g. MainTreeNodeValue and T).

4. Poor choice of variable names; e.g. mainT has an abbreviation: why not mainTree or root instead?

5. The Console.ReadLine(); at the end is uneccesary: it's for debugging only (so you can inspect the results before the console window auto-closes when you run a debugging session); instead, for debugging put a break-point on the closing curly brace of Main, and don't leave debug-only statements which impair the run-time behaviour.

6. Running the solution method has a (strange) side-effect on global/static data ...

   if (MainTreeNodeValue == 0)
       MainTreeNodeValue = T.x;
   

Can you give me an example of using a heap-based stack variable?

It's a neat technique, that I saw recently on this site.

When I said "heap-based" I meant that the local Stack variable stores its contents on the heap instead of on the program stack.

The first results of https://www.google.com/search?q=tree+recursion+stack are about traversing trees without recursion. It's something like:

class Solution
{
    public int solution(Tree root)
    {
        if (root == null)
            return 0;
        int rootValue = root.x;
        Stack<Tree> stack = new Stack<Tree>();
        stack.Push(root);
        int count = 0;
        while (stack.Count != 0)
        {
            Tree found = stack.Pop();
            if (found.x >= rootValue)
                ++count;
            if (found.l != null)
                stack.Push(found.l);
            if (found.r != null)
                stack.Push(found.r);
        }
        return count;
    }
}

Here's the same, modified for the requirement which is that:

• The descent should search the ever node in the tree (including invisible children)
• Nodes are counted (i.e. "visible") if they are at east as large as their largest ancestor.

using Pair = System.Tuple<Tree, int>;

class Solution
{
    public int solution(Tree root)
    {
        if (root == null)
            return 0;
        // A node of that tree containing value V is described as visible
        // if the path from the root of the tree to the node does not contain
        // a node with any value exceeding V.
        // So, store each Tree node together with an 'int' which represents
        // the highest V value found along that branch.
        Stack<Pair> stack = new Stack<Pair>();
        stack.Push(Tuple.Create(root, root.x));
        int count = 0;
        while (stack.Count != 0)
        {
            Pair tuple = stack.Pop();
            Tree found = tuple.Item1;
            int maxV = tuple.Item2;
            if (found.x >= maxV)
            {
                ++count;
                maxV = found.x;
            }
            if (found.l != null)
                stack.Push(Tuple.Create(found.l, maxV));
            if (found.r != null)
                stack.Push(Tuple.Create(found.r, maxV);
        }
        return count;
    }
}

Taking some pointers from other responses and adding my own 2 cents, a functional programming approach to this problem could look like this.

public class Node
{
    public int Value;
    public Node Left;
    public Node Right;

    public static int GetSolution(Node node, int maxValue = Int32.MinValue)
    {
        return
            node == null
                ? 0
                : node.Value >= maxValue
                        ?   (GetSolution(node.Left, node.Value)
                                + GetSolution(node.Right, node.Value)
                                + 1)
                        :   (GetSolution(node.Left, maxValue)
                                + GetSolution(node.Right, maxValue));

    }
}

This code uses recursive and a very simple way to counting the partial order of a tree. It uses traditional tree travel. I believe this is a good point to help the others to think about the new solution.

public class Tree {
public int v;
public Tree l;
public Tree r;

public int travelNode(Tree root) {
    int counter = 0;

    if (root != null && root.l != null){
        if (root.v <= root.l.v)
            counter +=1;
        counter +=travelNode(root.l);
    }
    if (root != null && root.r != null) {
        if (root.v <=root.r.v)
            counter +=1;
        counter +=travelNode(root.r);
    }
    return counter;
   }

   Tree(int v, Tree l, Tree r) {
       this.l = l;
       this.r = r;
       this.v =v;
   }
}

The tree can be built as

Tree root = new Tree(5, new Tree(3, new Tree(20, null, null),
    new Tree(21, null,null)), new Tree(10, new Tree(1, null, null), null));

The number of visible nodes are root.travelNode(root) + 1;.