Visible Tree Node | Number of Visible Nodes

Prereq: DFS on Tree

In a binary tree, we define a node "visible" when no node on the root-to-itself path (inclusive) has a greater value. The root is always "visible" since there are no other nodes between the root and itself. Given a binary tree, count the number of "visible" nodes.

Input:

Output: 3

For example: Node 4 is not visible since 5>4, similarly Node 3 is not visible since both 5>3 and 4>3. Node 8 is visible since all 5<=8, 4<=8, and 8<=8.

Try it yourself

Explanation

We can DFS on the tree and keep track of the max value we have seen as we go.

1. Decide on the return value

The problem asks for the total number of visible nodes, so we return the total number of visible nodes for the current subtree after we visit a node.

2. Identify states

The definition for a "visible" node is its value is greater than any other node's value on the root-to-itself path. To determine whether the current node is visible or not, we need to know the max value from the root to it. We can carry this as a state as we traverse down the tree.

Having decided on the state and return value we can now write the DFS.

Time Complexity: O(n)

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) which is O(n).

Space Complexity: O(h) stack memory where h is the height of the tree, which is O(n) in the worst case.

1class Node:
2    def __init__(self, val, left=None, right=None):
3        self.val = val
4        self.left = left
5        self.right = right
6
7def visible_tree_node(root: Node) -> int:
8    def dfs(root, max_sofar):
9        if not root:
10            return 0
11
12        total = 0
13        if root.val >= max_sofar:
14            total += 1
15
16        total += dfs(root.left, max(max_sofar, root.val)) # max_sofar for child node is the larger of previous max and current node val
17        total += dfs(root.right, max(max_sofar, root.val))
18
19        return total
20
21    # start max_sofar with smallest number possible so any value root has is smaller than it
22    return dfs(root, -float('inf'))
23
24# this function builds a tree from input; you don't have to modify it
25# learn more about how trees are encoded in https://algo.monster/problems/serializing_tree
26def build_tree(nodes, f):
27    val = next(nodes)
28    if val == 'x': return None
29    left = build_tree(nodes, f)
30    right = build_tree(nodes, f)
31    return Node(f(val), left, right)
32
33if __name__ == '__main__':
34    root = build_tree(iter(input().split()), int)
35    res = visible_tree_node(root)
36    print(res)
37
1import java.util.Arrays;
2import java.util.Iterator;
3import java.util.List;
4import java.util.Scanner;
5import java.util.function.Function;
6
7class Solution {
8    public static class Node<T> {
9        public T val;
10        public Node<T> left;
11        public Node<T> right;
12
13        public Node(T val) {
14            this(val, null, null);
15        }
16
17        public Node(T val, Node<T> left, Node<T> right) {
18            this.val = val;
19            this.left = left;
20            this.right = right;
21        }
22    }
23
24    private static int dfs(Node<Integer> root, int maxSoFar) {
25        if (root == null) return 0;
26        int total = 0;
27        if (root.val >= maxSoFar) {
28            total++;
29        }
30        // maxSoFar of the child node is the larger value of previous max and current node val
31        total += dfs(root.left, Math.max(maxSoFar, root.val));
32        total += dfs(root.right, Math.max(maxSoFar, root.val));
33
34        return total;
35    }
36
37    public static int visibleTreeNode(Node<Integer> root) {
38        // Start maxSoFar with smallest integer value possible so any value root has is greater than it
39        return dfs(root, Integer.MIN_VALUE);
40    }
41
42    // this function builds a tree from input; you don't have to modify it
43    // learn more about how trees are encoded in https://algo.monster/problems/serializing_tree
44    public static <T> Node<T> buildTree(Iterator<String> iter, Function<String, T> f) {
45        String val = iter.next();
46        if (val.equals("x")) return null;
47        Node<T> left = buildTree(iter, f);
48        Node<T> right = buildTree(iter, f);
49        return new Node<T>(f.apply(val), left, right);
50    }
51
52    public static List<String> splitWords(String s) {
53        return s.isEmpty() ? List.of() : Arrays.asList(s.split(" "));
54    }
55
56    public static void main(String[] args) {
57        Scanner scanner = new Scanner(System.in);
58        Node<Integer> root = buildTree(splitWords(scanner.nextLine()).iterator(), Integer::parseInt);
59        scanner.close();
60        int res = visibleTreeNode(root);
61        System.out.println(res);
62    }
63}
64
1using System;
2using System.Collections.Generic;
3using System.Linq;
4
5class Solution
6{
7    public class Node<T> 
8    {
9        public T val;
10        public Node<T> left;
11        public Node<T> right;
12
13        public Node(T val) 
14        {
15            this.val = val;
16        }
17
18        public Node(T val, Node<T> left, Node<T> right) 
19        {
20            this.val = val;
21            this.left = left;
22            this.right = right;
23        }
24    }
25
26    private static int Dfs(Node<int> root, int maxSoFar)
27    {
28        if (root == null) return 0;
29        int total = 0;
30        if (root.val >= maxSoFar)
31        {
32            total++;
33        }
34        // maxSoFar of the child node is the larger value of previous max and current node val
35        total += Dfs(root.left, Math.Max(maxSoFar, root.val));
36        total += Dfs(root.right, Math.Max(maxSoFar, root.val));
37
38        return total;
39    }
40
41    public static int VisibleTreeNode(Node<int> root)
42    {
43        // Start maxSoFar with smallest integer value possible so any value root has is greater than it
44        return Dfs(root, int.MinValue);
45    }
46
47    // this function builds a tree from input; you don't have to modify it
48    // learn more about how trees are encoded in https://algo.monster/problems/serializing_tree
49    public static Node<T> BuildTree<T>(List<string> strs, ref int pos, Func<string, T> f)
50    {
51        string val = strs[pos];
52        pos++;
53        if (val == "x") return null;
54        Node<T> left = BuildTree<T>(strs, ref pos, f);
55        Node<T> right = BuildTree<T>(strs, ref pos, f);
56        return new Node<T>(f(val), left, right);
57    }
58
59    public static List<string> SplitWords(string s)
60    {
61      return string.IsNullOrEmpty(s) ? new List<string>() : s.Trim().Split(' ').ToList();
62    }
63
64    public static void Main()
65    {
66        List<string> strs = SplitWords(Console.ReadLine());
67        int pos = 0;
68        Node<int> root = BuildTree(strs, ref pos, int.Parse);
69        int res = VisibleTreeNode(root);
70        Console.WriteLine(res);
71    }
72}
73
1class Node {
2    constructor(val, left = null, right = null) {
3        this.val = val;
4        this.left = left;
5        this.right = right;
6    }
7}
8
9function dfs(root, max_sofar) {
10    if (!root) return 0;
11    let total = 0;
12    if (root.val >= max_sofar) total++;
13
14    // max_sofar for child node is the larger of previous max and current node val
15    total += dfs(root.left, Math.max(max_sofar, root.val));
16    total += dfs(root.right, Math.max(max_sofar, root.val));
17
18    return total;
19}
20
21function visibleTreeNode(root) {
22    // start max_sofar with smallest number possible so any value root has is greater than it
23    return dfs(root, Number.NEGATIVE_INFINITY);
24}
25
26// this function builds a tree from input; you don't have to modify it
27// learn more about how trees are encoded in https://algo.monster/problems/serializing_tree
28function buildTree(nodes, f) {
29    const val = nodes.next().value;
30    if (val === 'x') return null;
31    const left = buildTree(nodes, f);
32    const right = buildTree(nodes, f);
33    return new Node(f(val), left, right);
34}
35
36function splitWords(s) {
37    return s == "" ? [] : s.split(' ');
38}
39
40function* main() {
41    const root = buildTree(splitWords(yield)[Symbol.iterator](), parseInt);
42    const res = visibleTreeNode(root);
43    console.log(res);
44}
45
46class EOFError extends Error {}
47{
48    const gen = main();
49    const next = (line) => gen.next(line).done && process.exit();
50    let buf = '';
51    next();
52    process.stdin.setEncoding('utf8');
53    process.stdin.on('data', (data) => {
54        const lines = (buf + data).split('\n');
55        buf = lines.pop();
56        lines.forEach(next);
57    });
58    process.stdin.on('end', () => {
59        buf && next(buf);
60        gen.throw(new EOFError());
61    });
62}
63
1#include <algorithm> // copy
2#include <iostream> // cin, cout
3#include <iterator> // back_inserter, istream_iterator
4#include <limits> // numeric_limits
5#include <sstream> // istringstream
6#include <string> // getline, stoi, string
7#include <vector> // vector
8
9template <typename T>
10struct Node {
11    T val;
12    Node<T>* left;
13    Node<T>* right;
14
15    explicit Node(T val, Node<T>* left = nullptr, Node<T>* right = nullptr)
16        : val{val}, left{left}, right{right} {}
17
18    ~Node() {
19        delete left;
20        delete right;
21    }
22};
23
24int dfs(Node<int>* root, int max_sofar) {
25    if (!root) return 0;
26    int total = 0;
27    if (root->val >= max_sofar) total++;
28    total += dfs(root->left, std::max(max_sofar, root->val));
29    total += dfs(root->right, std::max(max_sofar, root->val));
30    return total;
31}
32
33int visible_tree_node(Node<int>* root) {
34    // start max_sofar with smallest number possible so any value root has is greater than it
35    return dfs(root, std::numeric_limits<int>::min());
36}
37
38// this function builds a tree from input
39// learn more about how trees are encoded in https://algo.monster/problems/serializing_tree
40template<typename T, typename Iter, typename F>
41Node<T>* build_tree(Iter& it, F f) {
42    std::string val = *it;
43    ++it;
44    if (val == "x") return nullptr;
45    Node<T>* left = build_tree<T>(it, f);
46    Node<T>* right = build_tree<T>(it, f);
47    return new Node<T>{f(val), left, right};
48}
49
50template<typename T>
51std::vector<T> get_words() {
52    std::string line;
53    std::getline(std::cin, line);
54    std::istringstream ss{line};
55    std::vector<T> v;
56    std::copy(std::istream_iterator<T>{ss}, std::istream_iterator<T>{}, std::back_inserter(v));
57    return v;
58}
59
60int main() {
61    std::vector<std::string> root_vec = get_words<std::string>();
62    auto root_it = root_vec.begin();
63    Node<int>* root = build_tree<int>(root_it, [](auto s) { return std::stoi(s); });
64    int res = visible_tree_node(root);
65    std::cout << res << '\n';
66}
67
1import Control.Monad.Trans.State (State, evalState, state)
2import qualified Data.List as L
3import Data.Maybe (fromJust)
4
5data Tree a
6  = Empty
7  | Node a (Tree a) (Tree a)
8  deriving (Show)
9
10visibleTreeNode :: Tree Int -> Int
11-- start maxSoFar with smallest number possible so any value root has is greater than it
12visibleTreeNode = dfs minBound
13  where
14    dfs _ Empty = 0
15    dfs maxSoFar (Node a l r) =
16      (if a >= maxSoFar then 1 else 0)
17        -- maxSoFar for child node is the larger of previous max and current node val
18        + dfs (max maxSoFar a) l
19        + dfs (max maxSoFar a) r
20
21buildTree :: (String -> a) -> State [String] (Tree a)
22buildTree f = do
23  val <- state $ fromJust . L.uncons
24  if val == "x"
25    then pure Empty
26    else Node (f val) <$> buildTree f <*> buildTree f
27
28main :: IO ()
29main = do
30  root <- evalState (buildTree read) . words <$> getLine
31  let res = visibleTreeNode root
32  print res
33

Still not clear?Β SubmitΒ the part you don't understand to our editors.