+3 votes
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.
in Backtracking/DFS/BFS by (180 points)

3 Answers

+1 vote
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)
by (144 points)
0 votes

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 ck, if node_cnt[ck] <= n/2 and node_cnt[f] - node_cnt[i]  <= n/2, the node is answer. //O(n)

The total cost is O(n).

by AlgoStar (440 points)
0 votes
It seems that there is no good way, it is necessary to traverse most non-leaf nodes
by AlgoMeister (964 points)
The Book: Analysis and Design of Algorithms | Presentations on Slideshare | Lecture Notes, etc
...