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) {
26            return 0;
27        }
28        int total = 0;
29        if (root.val >= maxSoFar) {
30            total++;
31        }
32        // maxSoFar of the child node is the larger value of previous max and current node val
33        int newMax = Math.max(maxSoFar, root.val);
34        total += dfs(root.left, newMax);
35        total += dfs(root.right, newMax);
36
37        return total;
38    }
39
40    public static int visibleTreeNode(Node<Integer> root) {
41        // Start maxSoFar with smallest integer value possible so any value root has is greater than it
42        int result = dfs(root, Integer.MIN_VALUE);
43        return result;
44    }
45
46    // this function builds a tree from input; you don't have to modify it
47    // learn more about how trees are encoded in https://algo.monster/problems/serializing_tree
48    public static <T> Node<T> buildTree(Iterator<String> iter, Function<String, T> f) {
49        String val = iter.next();
50        if (val.equals("x")) return null;
51        Node<T> left = buildTree(iter, f);
52        Node<T> right = buildTree(iter, f);
53        return new Node<T>(f.apply(val), left, right);
54    }
55
56    public static List<String> splitWords(String s) {
57        return s.isEmpty() ? List.of() : Arrays.asList(s.split(" "));
58    }
59
60    public static void main(String[] args) {
61        Scanner scanner = new Scanner(System.in);
62        Node<Integer> root = buildTree(splitWords(scanner.nextLine()).iterator(), Integer::parseInt);
63        scanner.close();
64        int res = visibleTreeNode(root);
65        System.out.println(res);
66    }
67}
68

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)
29        {
30            return 0;
31        }
32        int total = 0;
33        if (root.val >= maxSoFar)
34        {
35            total++;
36        }
37        // maxSoFar of the child node is the larger value of previous max and current node val
38        int newMax = Math.Max(maxSoFar, root.val);
39        total += Dfs(root.left, newMax);
40        total += Dfs(root.right, newMax);
41
42        return total;
43    }
44
45    public static int VisibleTreeNode(Node<int> root)
46    {
47        // Start maxSoFar with smallest integer value possible so any value root has is greater than it
48        int result = Dfs(root, int.MinValue);
49        return result;
50    }
51
52    // this function builds a tree from input; you don't have to modify it
53    // learn more about how trees are encoded in https://algo.monster/problems/serializing_tree
54    public static Node<T> BuildTree<T>(List<string> strs, ref int pos, Func<string, T> f)
55    {
56        string val = strs[pos];
57        pos++;
58        if (val == "x") return null;
59        Node<T> left = BuildTree<T>(strs, ref pos, f);
60        Node<T> right = BuildTree<T>(strs, ref pos, f);
61        return new Node<T>(f(val), left, right);
62    }
63
64    public static List<string> SplitWords(string s)
65    {
66        return string.IsNullOrEmpty(s) ? new List<string>() : s.Trim().Split(' ').ToList();
67    }
68
69    public static void Main()
70    {
71        List<string> rootWords = SplitWords(Console.ReadLine());
72        int rootPos = 0;
73        Node<int> root = BuildTree(rootWords, ref rootPos, int.Parse);
74        int res = VisibleTreeNode(root);
75        Console.WriteLine(res);
76    }
77}
78

1"use strict";
2
3class Node {
4    constructor(val, left = null, right = null) {
5        this.val = val;
6        this.left = left;
7        this.right = right;
8    }
9}
10
11function dfs(root, maxSoFar) {
12    if (!root) {
13        return 0;
14    }
15    let total = 0;
16    if (root.val >= maxSoFar) {
17        total++;
18    }
19
20    // maxSoFar for child node is the larger of previous max and current node val
21    const newMax = Math.max(maxSoFar, root.val);
22    total += dfs(root.left, newMax);
23    total += dfs(root.right, newMax);
24
25    return total;
26}
27
28function visibleTreeNode(root) {
29    // start maxSoFar with smallest number possible so any value root has is greater than it
30    const result = dfs(root, Number.NEGATIVE_INFINITY);
31    return result;
32}
33
34// this function builds a tree from input; you don't have to modify it
35// learn more about how trees are encoded in https://algo.monster/problems/serializing_tree
36function buildTree(nodes, f) {
37    const val = nodes.next().value;
38    if (val === "x") return null;
39    const left = buildTree(nodes, f);
40    const right = buildTree(nodes, f);
41    return new Node(f(val), left, right);
42}
43
44function splitWords(s) {
45    return s === "" ? [] : s.split(" ");
46}
47
48function* main() {
49    const root = buildTree(splitWords(yield)[Symbol.iterator](), parseInt);
50    const res = visibleTreeNode(root);
51    console.log(res);
52}
53
54class EOFError extends Error {}
55{
56    const gen = main();
57    const next = (line) => gen.next(line).done && process.exit();
58    let buf = "";
59    next();
60    process.stdin.setEncoding("utf8");
61    process.stdin.on("data", (data) => {
62        const lines = (buf + data).split("\n");
63        buf = lines.pop();
64        lines.forEach(next);
65    });
66    process.stdin.on("end", () => {
67        buf && next(buf);
68        gen.throw(new EOFError());
69    });
70}
71

1class BinaryTreeNode<T> {
2    val: T;
3    left: BinaryTreeNode<T> | null;
4    right: BinaryTreeNode<T> | null;
5    constructor(val: T, left: BinaryTreeNode<T> | null = null, right: BinaryTreeNode<T> | null = null) {
6        this.val = val;
7        this.left = left;
8        this.right = right;
9    }
10}
11
12function dfs(root: any, maxSoFar: number): number {
13    if (!root) {
14        return 0;
15    }
16    let total = 0;
17    if (root.val >= maxSoFar) {
18        total++;
19    }
20    const newMax = Math.max(maxSoFar, root.val);
21    total += dfs(root.left, newMax);
22    total += dfs(root.right, newMax);
23    return total;
24}
25
26function visibleTreeNode(root: any): number {
27    const result = dfs(root, Number.NEGATIVE_INFINITY);
28    return result;
29}
30
31// this function builds a tree from input; you don't have to modify it
32// learn more about how trees are encoded in https://algo.monster/problems/serializing_tree
33function buildTree<T>(nodes: Iterator<string>, f: (val: string) => T): BinaryTreeNode<T> | null {
34    const val = nodes.next().value;
35    if (val === "x") return null;
36    const left = buildTree(nodes, f);
37    const right = buildTree(nodes, f);
38    return new BinaryTreeNode(f(val), left, right);
39}
40
41function splitWords(s: string): string[] {
42    return s === "" ? [] : s.split(" ");
43}
44
45function* main() {
46    const root = buildTree(splitWords(yield)[Symbol.iterator](), parseInt);
47    const res = visibleTreeNode(root);
48    console.log(res);
49}
50
51class EOFError extends Error {}
52{
53    const gen = main();
54    const next = (line?: string) => gen.next(line ?? "").done && process.exit();
55    let buf = "";
56    next();
57    process.stdin.setEncoding("utf8");
58    process.stdin.on("data", (data: string) => {
59        const lines = (buf + data).split("\n");
60        buf = lines.pop() ?? "";
61        lines.forEach(next);
62    });
63    process.stdin.on("end", () => {
64        buf && next(buf);
65        gen.throw(new EOFError());
66    });
67}
68

1#include <algorithm>
2#include <iostream>
3#include <iterator>
4#include <limits>
5#include <sstream>
6#include <string>
7#include <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) {
26        return 0;
27    }
28    int total = 0;
29    if (root->val >= max_sofar) {
30        total++;
31    }
32    int new_max = std::max(max_sofar, root->val);
33    total += dfs(root->left, new_max);
34    total += dfs(root->right, new_max);
35    return total;
36}
37
38int visible_tree_node(Node<int>* root) {
39    // start max_sofar with smallest number possible so any value root has is greater than it
40    int result = dfs(root, std::numeric_limits<int>::min());
41    return result;
42}
43
44// this function builds a tree from input
45// learn more about how trees are encoded in https://algo.monster/problems/serializing_tree
46template<typename T, typename Iter, typename F>
47Node<T>* build_tree(Iter& it, F f) {
48    std::string val = *it;
49    ++it;
50    if (val == "x") return nullptr;
51    Node<T>* left = build_tree<T>(it, f);
52    Node<T>* right = build_tree<T>(it, f);
53    return new Node<T>{f(val), left, right};
54}
55
56template<typename T>
57std::vector<T> get_words() {
58    std::string line;
59    std::getline(std::cin, line);
60    std::istringstream ss{line};
61    ss >> std::boolalpha;
62    std::vector<T> v;
63    std::copy(std::istream_iterator<T>{ss}, std::istream_iterator<T>{}, std::back_inserter(v));
64    return v;
65}
66
67int main() {
68    std::vector<std::string> root_vec = get_words<std::string>();
69    auto root_it = root_vec.begin();
70    Node<int>* root = build_tree<int>(root_it, [](auto s) { return std::stoi(s); });
71    int res = visible_tree_node(root);
72    std::cout << res << '\n';
73}
74

1use std::error;
2use std::io;
3use std::str::FromStr;
4
5pub type Tree<T> = Option<Box<Node<T>>>;
6
7pub struct Node<T> {
8    pub val: T,
9    pub left: Tree<T>,
10    pub right: Tree<T>,
11}
12
13fn dfs(root: &Tree<i32>, max_sofar: i32) -> i32 {
14    match root {
15        None => 0,
16        Some(node) => {
17            let mut total = 0;
18            if node.val >= max_sofar {
19                total += 1;
20            }
21            let new_max = std::cmp::max(max_sofar, node.val);
22            total += dfs(&node.left, new_max);
23            total += dfs(&node.right, new_max);
24            total
25        }
26    }
27}
28
29fn visible_tree_node(root: Tree<i32>) -> i32 {
30    // start max_sofar with smallest number possible so any value root has is greater than it
31    let result = dfs(&root, i32::MIN);
32    result
33}
34
35// this function builds a tree from input
36// learn more about how trees are encoded in https://algo.monster/problems/serializing_tree
37fn build_tree<'a, T, I>(nodes: &mut I) -> Result<Tree<T>, Box<dyn error::Error>>
38where
39    T: FromStr,
40    I: Iterator<Item = &'a str>,
41    <T as FromStr>::Err: 'static + error::Error,
42{
43    let val = match nodes.next().ok_or("eol")? {
44        "x" => return Ok(None),
45        v => v.parse()?,
46    };
47    let left = build_tree(nodes)?;
48    let right = build_tree(nodes)?;
49    Ok(Some(Box::new(Node { val, left, right })))
50}
51
52fn main() -> Result<(), Box<dyn error::Error>> {
53    let mut line = String::new();
54    io::stdin().read_line(&mut line)?;
55    let root = build_tree(&mut line.split_whitespace())?;
56    let res = visible_tree_node(root);
57    println!("{}", res);
58    Ok(())
59}
60

1package main
2
3import (
4    "bufio"
5    "fmt"
6    "math"
7    "os"
8    "strconv"
9    "strings"
10)
11
12type Node struct {
13    val   int
14    left  *Node
15    right *Node
16}
17
18func dfs(root *Node, maxSoFar int) int {
19    if root == nil {
20        return 0
21    }
22    total := 0
23    if root.val >= maxSoFar {
24        total++
25    }
26    // maxSoFar for child node is the larger of previous max and current node value
27    newMax := int(math.Max(float64(maxSoFar), float64(root.val)))
28    total += dfs(root.left, newMax)
29    total += dfs(root.right, newMax)
30    return total
31}
32
33func visibleTreeNode(root *Node) int {
34    // Start maxSoFar with the smallest number possible so that any value root has is smaller than it
35    result := dfs(root, math.MinInt32)
36    return result
37}
38
39// this function builds a tree from input; you don't have to modify it
40// learn more about how trees are encoded in https://algo.monster/problems/serializing_tree
41func buildTree(nodes []string, pos *int) *Node {
42    val := nodes[*pos]
43    *pos++
44    if val == "x" {
45        return nil
46    }
47    v, _ := strconv.Atoi(val)
48    left := buildTree(nodes, pos)
49    right := buildTree(nodes, pos)
50    return &Node{v, left, right}
51}
52
53func splitWords(s string) []string {
54    if s == "" {
55        return []string{}
56    }
57    return strings.Split(s, " ")
58}
59
60func main() {
61    scanner := bufio.NewScanner(os.Stdin)
62    scanner.Scan()
63    rootIdx := 0
64    root := buildTree(splitWords(scanner.Text()), &rootIdx)
65    res := visibleTreeNode(root)
66    fmt.Println(res)
67}
68

1Node = Struct.new('Node', :val, :left, :right)
2
3def dfs(root, max_sofar)
4  unless root
5    return 0
6  end
7  total = 0
8  if root.val >= max_sofar
9    total += 1
10  end
11  new_max = [max_sofar, root.val].max
12  total += dfs(root.left, new_max)
13  total += dfs(root.right, new_max)
14  total
15end
16
17def visible_tree_node(root)
18  # start max_sofar with smallest number possible so any value root has is greater than it
19  result = dfs(root, -Float::INFINITY)
20  result
21end
22
23# this function builds a tree from input; you don't have to modify it
24# learn more about how trees are encoded in https://algo.monster/problems/serializing_tree
25def build_tree(nodes, &f)
26  val = nodes.next
27  return nil if val == 'x'
28  left = build_tree(nodes, &f)
29  right = build_tree(nodes, &f)
30  Node.new(f.call(val), left, right)
31end
32
33if __FILE__ == $0
34  root = build_tree(gets.split.each) { |v| Integer(v, 10) }
35  res = visible_tree_node(root)
36  puts(res)
37end
38

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 root =
13  let result = dfs minBound root
14   in result
15  where
16    dfs maxSoFar current =
17      case current of
18        Empty -> 0
19        Node a l r ->
20          let total = 0
21              visibleTotal =
22                if a >= maxSoFar
23                  then total + 1
24                  else total
25              newMax = max maxSoFar a
26              -- maxSoFar for child node is the larger of previous max and current node val
27              leftTotal = dfs newMax l
28              totalAfterLeft = visibleTotal + leftTotal
29              rightTotal = dfs newMax r
30              result = totalAfterLeft + rightTotal
31           in result
32
33buildTree :: (String -> a) -> State [String] (Tree a)
34buildTree f = do
35  val <- state $ fromJust . L.uncons
36  if val == "x"
37    then pure Empty
38    else Node (f val) <$> buildTree f <*> buildTree f
39
40main :: IO ()
41main = do
42  root <- evalState (buildTree read) . words <$> getLine
43  let res = visibleTreeNode root
44  print res
45