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

ChenKaifeng's blog

By ChenKaifeng, history, 5 weeks ago, In English,

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.

 
 
 
 
  • Vote: I like it
  • -2
  • Vote: I do not like it

»
5 weeks ago, # |
  Vote: I like it 0 Vote: I do not like it

Probably a more basic question to answer first is: when is an unrooted tree a binary tree?

  • »
    »
    5 weeks ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    Well thats a simple question using dfs.

    If a tree is not a binary tree, it is clearly not a BST.

    • »
      »
      »
      5 weeks ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      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.