go_rob's blog

Partition a Binary Tree
By go_rob, history, 8 years ago, In English

Given a binary tree,

We have to remove a single edge and partition the tree into two new trees such that difference of their diameters remains less than a given constant k.

Please suggest me an approach of O(n) time complexity.

  • Vote: I like it
  • +12
  • Vote: I do not like it

»
8 years ago, # |
  Vote: I like it 0 Vote: I do not like it

Auto comment: topic has been updated by go_rob (previous revision, new revision, compare).

→ Reply
»
8 years ago, # |
  Vote: I like it 0 Vote: I do not like it

one way is to store the three longest paths starting at each vertex (note that each path should go through a distinct vertex), this can be done in O(N) and having this information you could easily choose an edge to remove and compute the diameter of each tree.

→ Reply
»
8 years ago, # |
← Rev. 3   Vote: I like it 0 Vote: I do not like it

I found a method but I don't think it is the best approach. It seems too messy for my taste — I would like to hear any better solutions!

Spoiler
→ Reply
»
8 years ago, # |
← Rev. 4   Vote: I like it +15 Vote: I do not like it

I am not sure about my solution, but looks reasonable to me.

----------------------spoiler-------------------------

so say u have a binary tree looks like

let f[i] represent the longest distance from i to any vertex in the subtree of i.

it is easy to get in o(n).

so consider we are deleting the edge from x to its father. (in the figure we assume x = 2)

therefore the tree is split into two parts, rooted by 2 and 1.

for 2, the diameter = f[lson]+f[rson]+1 (coz it is binary tree)

for 1, the diameter = f[rson]+1

so u can just bruteforce the deleted edge, and calculate the difference.

I think it is reasonable for me, but if there is something wrong or bug, please point it out, thanks a lot.

→ Reply
  • »
    »
    8 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    Your solution seems buggy.

    The two Eqn for the diameter that you have written doesn't hold true for many cases.

    → Reply
    • »
      »
      »
      8 years ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      ah sorry i misread the problem,

      so like, u make dp[i] to the diameter of the tree rooted by i.

      the same thing, then for 2, it looks like dp[2] straightly. for 1, it is max(dp[rson], f[rson]+1)

      is it work? sorry for the retarded previous answer :L

      → Reply
      • »
        »
        »
        »
        8 years ago, # ^ |
          Vote: I like it 0 Vote: I do not like it

        I don't think your solution will work in all cases. The max(dp[rson], f[rson] + 1) will not not always work.

        I am providing a better solution here

        → Reply
»
8 years ago, # |
  Vote: I like it 0 Vote: I do not like it

Guys, I have found out a solution using DP which will work in O(n) using 2 DFS. Here is the code, Please check the code and verify its correctness.

→ Reply