Count Special Nodes in Generic Tree
Given a generic tree, find the count of all special nodes. A node is a special node if there is a path from root to that node with all distinct elements. The input was not a pointer to a tree. He’d give me an adjacency list and an array of values where the value of ith node in the adjacency list is the ith element in the values array. He asked me not a create a tree out of the given information and rather do it with the adjacency list itself.

Question

Count Special Nodes in Generic Tree

Given a generic tree, find the count of all special nodes. A node is a special node if there is a path from root to that node with all distinct elements. The input was not a pointer to a tree. He’d give me an adjacency list and an array of values where the value of ith node in the adjacency list is the ith element in the values array. He asked me not a create a tree out of the given information and rather do it with the adjacency list itself.

Accepted Answer

I suggested to do a depth first search keeping a set which contains all elements upto a given node. Once I reach a particular node, I check if it’s already in the set. If its already in the set, I return because that element has already been visited and is not a special node. Otherwise, I increase the count of a global variable by 1 and push that element to the set. Then I go through the adjacency list of that element and call this function recursively. Once I return from the element after visiting its neighbors, I pop the element from the set. I told him the approach and he asked me to write the code for it. He was convinced with the approach and he liked the code.

Accepted Answer

DFS

We will do a recursive Depth First Search keeping a vector/list to check for the distinct element.

We start the recursive DFS from the “root” node with an empty vector/list.
Let’s say we are at some node “x” of the Tree with a vector/list containing all the elements from root to that node.
If the value of the node “x” is present in the vector/list then it means our distinct element condition is violating so return 0.
Else insert the value of node “x” in vector/list and initialize the count of special nodes with 1.
Now recurse for children of node “x” with updated vector/list to count the special nodes in subtree of “x”.
Now delete the value of node “x” from vector/list to make sure that all other child elements have been removed from the vector/list when we move to the next child
Return the total count of special nodes

Space Complexity: O(n)Explanation:

O(N), where N is the number of nodes in Generic Tree.

As we are doing recursive DFS which can at max have a depth of O(N) and also our vector/list can have max size N.

Time Complexity: O(n^2)Explanation:

O(N*N), where N is the number of nodes in Generic Tree.

As we are visiting each node of the tree once and checking if the value of the node already exists or not then pushing the value of nodes in vector/list, which is O(N) on average. So Overall Time Complexity is O(N*N).

Accepted Answer

HashMap/Dictionary Approach

We will do a recursive Depth First Search keeping a HashMap/Dictionary to check for the distinct element.

We start the recursive DFS from the “root” node with an empty HashMap/Dictionary
Let’s say we are at some node “x” of the Tree with a HashMap/Dictionary containing all the elements from root to that node
If the value of the node “x” is present in HashMap/Dictionary then it means our distinct element condition is violating so return 0
Else insert the value of node “x” in HashMap/Dictionary and initialize the count of special nodes with 1
Now recurse for children of node “x” with updated HashMap/Dictionary to count the special nodes in subtree of “x”.
Now delete the value of node “x” from HashMap/Dictionary to make sure that all other child elements have been removed from the vector/list when we move to the next child
Return the total count of special nodes

Space Complexity: O(n)Explanation:

O(N), where N is the number of nodes in Generic Tree.

As we are doing recursive DFS which can at max have a depth of O(N) and also our HashMap can have max size N.

Time Complexity: O(n)Explanation:

O(N), where N is the number of nodes in Generic Tree.

As we are visiting each node of the tree once and checking if the value of the node already exists or not then pushing the value of nodes in HashMap, which is O(1) on average. So Overall Time Complexity is O(N).

Top Amazon Software Developer interview questions & answers

Popular interview questions of Software Developer

Top HR questions asked in Amazon Software Developer