I saw this problem in Facebook Recruiting Portal.
I intended this code to traverse the tree from query nodes until the found the targer character.
Nodes in a Subtree
You are given a tree that contains N nodes, each containing an
integer u which corresponds to a lowercase character c in the string
s using 1-based indexing. You are required to answer Q queries of
type [u, c], where u is an integer and c is a lowercase letter. The
query result is the number of nodes in the subtree of node u
containing c.
Signature:
int[] countOfNodes(Node root, ArrayList<Query> queries, String s)
Input
A pointer to the root node, an array list containing Q queries of
type [u, c], and a string s
Constraints
N and Q are the integers between 1 and 1,000,000 u is an integer
between 1 and N s is of the length of N, containing only lowercase
letters c is a lowercase letter contained in string s Node 1 is the
root of the tree
Output
An integer array containing the response to each query
Example
1(a)
/ \
2(b) 3(a)s = "aba" RootNode = 1 query = [[1, 'a']]
Note: Node 1 corresponds to first letter 'a' Node 2 corresponds to
second letter of the string 'b', Node 3 corresponds to third letter
of the string 'a'.
output = [2]
Both Node 1 and Node 3 contain 'a', so the number of nodes within the
subtree of Node 1 containing 'a' is 2.
// Solution
int[] countOfNodes(Node root, ArrayList<Query> queries, String s) {
if (root == null) return new int[] { 0 }; // Return if empty tree
List<Integer> ans = new ArrayList<Integer>();
HashMap<Character, Integer> hm;
for (Query value : queries) {
char c = value.c;
int v = value.v;
Node curr = null;
hm = new HashMap<Character, Integer>();
if (root.val != v) { // If root is not in target query move on
for (Node val : root.children) {
if (val.val == v) { // Child node is the root for query
curr = val;
}
}
}
else {
curr = root;
}
if (curr != null) { // Traverse the n-ary Tree
traverse(curr, c, v, hm, s);
}
if (!hm.isEmpty()) { // Remove empty Hash
ans.add(hm.get(c));
}
}
return ans.stream().mapToInt(i -> i).toArray(); // Lambda array
}
public static void traverse(Node root, char c, int v,
HashMap<Character, Integer> hm, String s) {
if (root == null) return;
if (s.charAt(root.val - 1) == c) { // Save if match query
hm.put(c, hm.getOrDefault(c, 0) + 1);
}
for (Node value : root.children) { // Traverse the tree
traverse(value, c, v, hm, s);
}
return;
}
// Tree Node Definitions
class Node {
public int val;
public List<Node> children;
public Node() {
val = 0;
children = new ArrayList<Node>();
}
public Node(int _val) {
val = _val;
children = new ArrayList<Node>();
}
public Node(int _val, ArrayList<Node> _children) {
val = _val;
children = _children;
}
}
class Query {
int v;
char c;
Query(int v, char c) {
this.v = v;
this.c = c;
}
}