Sense Coding Interview / Online Assessment: Validate an N-ary Tree and Count Univalue Subtrees

Part 1: Validate if a given tree is a unival tree.

Part 2: Count the number of unival subtrees.

A unival tree is an n-ary tree in which all nodes have the same value.

Examples:

This is a valid unival tree:

1

This is not:

1
  1
    1 1 2
      1 1

This has 8 unival subtrees:

1
/ \
2   3
/ \ / \
2 2 3 3
/ \ / \ / \
5 5 4 4 3 3

Emp => {id: int, name: string, mid: int}

Write a function which takes input as a list of Emp(s), prints out the org chart as follows:

Eric
|__ Jack
|   |__ Viral
|   |__ Michael
|       |__ George
|   |__ Ryan
|__ Nitesh

This prompt combines two tree tasks. First, determine whether an N-ary tree is a unival tree, meaning every node has the same value. Second, count how many unival subtrees exist in a tree. The standard approach is DFS or postorder traversal: evaluate each subtree from the bottom up, check whether all children match the current node, and accumulate the number of valid subtrees along the way. The org chart part can be solved by building a manager-to-employee tree from the input records and printing it recursively in hierarchical order.