Please, try EDU on Codeforces! New educational section with videos, subtitles, texts, and problems. ×

### ChenKaifeng's blog

By ChenKaifeng, history, 5 weeks ago, ,

I came up with an idea when I'm having Math Exam XD, it is like this:

We have a no-root-tree with weight on each node, can we find a node as root and the tree is a BST looking at the weight of the point in less than $O(n^2)$? (this is a yes or no problem)

If it is possible, how? And if we need to get the exact Node?

I've tried using the BST through to do this, but the problem is harder than I expected...

Thanks a lot.

• -2

 » 5 weeks ago, # |   0 Probably a more basic question to answer first is: when is an unrooted tree a binary tree?
•  » » 5 weeks ago, # ^ |   0 Well thats a simple question using dfs.If a tree is not a binary tree, it is clearly not a BST.
•  » » » 5 weeks ago, # ^ |   0 I don't believe "when is an unrooted tree a binary tree?" requires DFS — in fact I am guessing any tree with the degree of each vertex $\leq 3$ is a binary tree.