Finding non-leaf node of a tree with no large subtrees

Question

When you create a non-leaf node of a tree, you create more than 1 subtree. Given a tree with n nodes, give an algorithm to find a non-leaf node v, such that deletion of node v leaves no subtree with more than n/2 nodes.

Answer 1

First, randomly pick up a node and apply DFS to calculate the number of nodes for each of its branch (step 1)

If none of its branch has the number of nodes bigger than n/2, it is the node we want

If one of its branch does have more than n/2 nodes, then pick up the node in this branch to do step 1

this seems like the partition process in Quick Select which narrows the range after each search

the worst case can be n times of attempts to finally pick the correct node

and the average is less than n times for the selection

each DFS consumes O(n) time

thus, the total time complexity is O(n^2)

Answer 2

1. Recursively calculate the number of node in sub-tree with each node. //O(n)

2. DFS the tree; for each node i, father of the node f, and its children c_k, if node_cnt[c_k] <= n/2 and node_cnt[f] - node_cnt[i]  <= n/2, the node is answer. //O(n)

The total cost is O(n).