Binary Tree Visible Nodes

A coding challenge from Microsoft interviews involving binary trees and path visibility.

Problem Statement

Given a binary tree T consisting of N nodes, count the number of visible nodes.

Definitions

• Binary tree: Either an empty tree or a node (called the root) made of a single integer value and two further binary trees (left subtree and right subtree)
• Path: A non-empty sequence of nodes that one can go through by following pointers
• Path length: The number of pointers a path follows
• Height: The length of the longest possible path in the tree (empty tree has height -1, single node has height 0)
• Visible node: A node with value V is visible if the path from the root to that node does not have any node with value exceeding V. The root is always visible, and nodes with values lower than their ancestors are never visible.

Tree Structure

class Tree {
    public int x;
    public Tree l;  // left subtree
    public Tree r;  // right subtree
}

Examples

Example 1:

        5
       / \
      3   10
     /\    \
   20 21    1

• Visible nodes: 5, 10, 20, 21 (4 nodes)
• Node with value 1 is NOT visible because there’s a node with value 10 on the path from root to it
• Node with value 3 is NOT visible because its value is lower than that of the root (5)

Example 2:

        8
       / \
      2   6
     /\
    8  7

• The function should return 2
• Only visible nodes are those with value 8

Solution

using System;

class Solution
{
    public int solution(Tree T)
    {
        if (T == null)
            return 0;

        return CountVisibleNodes(T, int.MinValue);
    }

    private int CountVisibleNodes(Tree node, int maxSoFar)
    {
        if (node == null)
            return 0;

        int count = 0;

        // A node is visible if its value >= all values on the path from root
        if (node.x >= maxSoFar)
        {
            count = 1;
            maxSoFar = node.x;  // Update the max for children
        }

        // Recursively check left and right subtrees
        count += CountVisibleNodes(node.l, maxSoFar);
        count += CountVisibleNodes(node.r, maxSoFar);

        return count;
    }
}

// Tree class definition
class Tree
{
    public int x;
    public Tree l;
    public Tree r;

    public Tree(int value)
    {
        x = value;
    }
}

Solution Explanation

Algorithm

1. Start from the root with maxSoFar = int.MinValue
2. At each node, check if node.value >= maxSoFar
   • If yes, the node is visible; increment count and update maxSoFar
   • If no, the node is not visible; continue with same maxSoFar
3. Recursively process left and right subtrees
4. Return total count

Complexity Analysis

• Time Complexity: O(N) - each node is visited exactly once
• Space Complexity: O(H) - where H is the height of the tree (recursive call stack)
  • Best case: O(log N) for balanced tree
  • Worst case: O(N) for skewed tree

Test Cases

// Test case 1: Example from problem
var tree1 = new Tree(5)
{
    l = new Tree(3)
    {
        l = new Tree(20),
        r = new Tree(21)
    },
    r = new Tree(10)
    {
        r = new Tree(1)
    }
};
Console.WriteLine(solution(tree1));  // Expected: 4

// Test case 2: Second example
var tree2 = new Tree(8)
{
    l = new Tree(2)
    {
        l = new Tree(8),
        r = new Tree(7)
    },
    r = new Tree(6)
};
Console.WriteLine(solution(tree2));  // Expected: 2

// Test case 3: Empty tree
Console.WriteLine(solution(null));   // Expected: 0

// Test case 4: Single node
var tree3 = new Tree(1);
Console.WriteLine(solution(tree3));  // Expected: 1

// Test case 5: All nodes increasing (all visible)
var tree4 = new Tree(1)
{
    l = new Tree(2)
    {
        l = new Tree(3)
    }
};
Console.WriteLine(solution(tree4));  // Expected: 3

Alternative Iterative Solution

public int SolutionIterative(Tree T)
{
    if (T == null)
        return 0;

    int count = 0;
    var stack = new Stack<(Tree node, int maxSoFar)>();
    stack.Push((T, int.MinValue));

    while (stack.Count > 0)
    {
        var (node, maxSoFar) = stack.Pop();

        if (node == null)
            continue;

        int newMax = maxSoFar;
        if (node.x >= maxSoFar)
        {
            count++;
            newMax = node.x;
        }

        stack.Push((node.l, newMax));
        stack.Push((node.r, newMax));
    }

    return count;
}

Key Insights

1. Visibility depends on path, not siblings - A node can be visible even if its sibling has a higher value
2. Root is always visible - int.MinValue ensures the root is always counted
3. DFS is natural - We need to maintain state (maxSoFar) along each path

Sources

• C#/Intrebari interviu/Interviu Microsoft/problema2_1.png
• C#/Intrebari interviu/Interviu Microsoft/problema2_2.png