Visible Tree Node | Number of Visible Nodes
Prereq: DFS on Tree
In a binary tree, a node is labeled as "visible" if, on the path from the root to that node, there isn't any node with a value higher than this node's 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 at the end of each function call, we return the total number of visible nodes in the current subtree.
2. Identify states
The definition of a "visible" node is that no node on the root-to-itself path (inclusive) has a strictly greater value. This means its value is greater or equal to 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.
1from math import inf
2
3class Node:
4 def __init__(self, val, left=None, right=None):
5 self.val = val
6 self.left = left
7 self.right = right
8
9def visible_tree_node(root: Node) -> int:
10 def dfs(root, max_sofar):
11 if not root:
12 return 0
13
14 total = 0
15 if root.val >= max_sofar:
16 total += 1
17
18 # max_sofar for child node is the larger of previous max and current node val
19 total += dfs(root.left, max(max_sofar, root.val))
20 total += dfs(root.right, max(max_sofar, root.val))
21
22 return total
23
24 # start max_sofar with smallest number possible so any value root has is smaller than it
25 return dfs(root, -inf)
26
27# this function builds a tree from input; you don't have to modify it
28# learn more about how trees are encoded in https://algo.monster/problems/serializing_tree
29def build_tree(nodes, f):
30 val = next(nodes)
31 if val == "x":
32 return None
33 left = build_tree(nodes, f)
34 right = build_tree(nodes, f)
35 return Node(f(val), left, right)
36
37if __name__ == "__main__":
38 root = build_tree(iter(input().split()), int)
39 res = visible_tree_node(root)
40 print(res)
411import 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}
641using 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}
731"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) return 0;
13 let total = 0;
14 if (root.val >= maxSoFar) total++;
15
16 // maxSoFar for child node is the larger of previous max and current node val
17 total += dfs(root.left, Math.max(maxSoFar, root.val));
18 total += dfs(root.right, Math.max(maxSoFar, root.val));
19
20 return total;
21}
22
23function visibleTreeNode(root) {
24 // start maxSoFar with smallest number possible so any value root has is greater than it
25 return dfs(root, Number.NEGATIVE_INFINITY);
26}
27
28// this function builds a tree from input; you don't have to modify it
29// learn more about how trees are encoded in https://algo.monster/problems/serializing_tree
30function buildTree(nodes, f) {
31 const val = nodes.next().value;
32 if (val === "x") return null;
33 const left = buildTree(nodes, f);
34 const right = buildTree(nodes, f);
35 return new Node(f(val), left, right);
36}
37
38function splitWords(s) {
39 return s === "" ? [] : s.split(" ");
40}
41
42function* main() {
43 const root = buildTree(splitWords(yield)[Symbol.iterator](), parseInt);
44 const res = visibleTreeNode(root);
45 console.log(res);
46}
47
48class EOFError extends Error {}
49{
50 const gen = main();
51 const next = (line) => gen.next(line).done && process.exit();
52 let buf = "";
53 next();
54 process.stdin.setEncoding("utf8");
55 process.stdin.on("data", (data) => {
56 const lines = (buf + data).split("\n");
57 buf = lines.pop();
58 lines.forEach(next);
59 });
60 process.stdin.on("end", () => {
61 buf && next(buf);
62 gen.throw(new EOFError());
63 });
64}
651#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) 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 ss >> std::boolalpha;
56 std::vector<T> v;
57 std::copy(std::istream_iterator<T>{ss}, std::istream_iterator<T>{}, std::back_inserter(v));
58 return v;
59}
60
61int main() {
62 std::vector<std::string> root_vec = get_words<std::string>();
63 auto root_it = root_vec.begin();
64 Node<int>* root = build_tree<int>(root_it, [](auto s) { return std::stoi(s); });
65 int res = visible_tree_node(root);
66 std::cout << res << '\n';
67}
681package 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 total += dfs(root.left, int(math.Max(float64(maxSoFar), float64(root.val))))
28 total += dfs(root.right, int(math.Max(float64(maxSoFar), float64(root.val))))
29 return total
30}
31
32func visibleTreeNode(root *Node) int {
33 // Start maxSoFar with the smallest number possible so that any value root has is smaller than it
34 return dfs(root, math.MinInt32)
35}
36
37// this function builds a tree from input; you don't have to modify it
38// learn more about how trees are encoded in https://algo.monster/problems/serializing_tree
39func buildTree(nodes []string, pos *int) *Node {
40 val := nodes[*pos]
41 *pos++
42 if val == "x" {
43 return nil
44 }
45 v, _ := strconv.Atoi(val)
46 left := buildTree(nodes, pos)
47 right := buildTree(nodes, pos)
48 return &Node{v, left, right}
49}
50
51func splitWords(s string) []string {
52 if s == "" {
53 return []string{}
54 }
55 return strings.Split(s, " ")
56}
57
58func main() {
59 scanner := bufio.NewScanner(os.Stdin)
60 scanner.Scan()
61 rootIdx := 0
62 root := buildTree(splitWords(scanner.Text()), &rootIdx)
63 res := visibleTreeNode(root)
64 fmt.Println(res)
65}
661import 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