biximo's blog

Proving certain binary tree property
By biximo, history, 10 months ago, In English

I recently came across a claim about binary trees that I was unable to prove. Given a binary tree, $$$\sum{|child_l|\times |child_r| } = O(N^2)$$$

Could someone provide proof and/or a way to intuitively explain this?

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

»
10 months ago, # |
← Rev. 2   Vote: I like it +16 Vote: I do not like it

Actually, I guess I have some kind of intuitive explanation behind this. If we imagine that each node "contributes" to the $$$N^2$$$ count, we can observe that no matter how the tree is structured, the total number that it contributes will be maximum $$$N$$$, since once two subtrees "merge" they will no longer multiply within themselves to count towards the $$$N^2$$$. So, since each node will add a maximum of $$$N$$$ towards the count, the total number will add up to maximum $$$N^2$$$. I think I am more interested in formal proof.

→ Reply
»
10 months ago, # |
  Vote: I like it +37 Vote: I do not like it

Another way to think about it is that any pair of nodes $$$(u, v)$$$ is considered at most (exactly, in fact) once and this happens at their LCA.

→ Reply
»
10 months ago, # |
  Vote: I like it +23 Vote: I do not like it

Suppose we want to count number of pairs $$$(u, v)$$$ such that $$$LCA(u, v) = i$$$. If children of $$$i$$$ are $$$l$$$ and $$$r$$$, then the number is equal of $$$\text{SubtreeSize}(l) \times \text{SubtreeSize}(r)$$$ if we consider pairs $$$(u, v)$$$ and $$$(v, u)$$$ equal. Therefore the sum you mentioned is equal to total number of pairs of vertices in the tree (number of subsets of size two).

→ Reply
  • »
    »
    10 months ago, # ^ |
      Vote: I like it +8 Vote: I do not like it

    Total number of pairs except the ones $$$\{u,v\}$$$ where $$$u$$$ is an ancestor of $$$v$$$ since $$$LCA(u,v) = u$$$ but this is not counted in $$$\text{SubtreeSize} (l_u) \times \text{SubtreeSize} (r_u)$$$

    → Reply
»
10 months ago, # |
  Vote: I like it +18 Vote: I do not like it

The given sum is same as the union of cross products of sets of vertoces of left and right subtrees. Now we can see that each unordered pair of vertices $$$(u,v)$$$ occurs atmost once in the above union. This also gives an upper bound of $$$N*(N-1)/2$$$

→ Reply
»
10 months ago, # |
  Vote: I like it +8 Vote: I do not like it

https://codeforces.me/blog/entry/124538?#comment-1105664

→ Reply