9
$\begingroup$

If for a given binary tree:

  • Every node with 2 children has a weight of 3
  • Every node with only 1 child has a weight of 2
  • Every node with no children (a leaf) has a weight of 1
  • The weight of a binary tree is the sum of all its nodes' weights

For example, the weight of this binary tree is 11:

example

If $n$ is the number of nodes in the tree, what is the maximum and minimum weight of a binary tree?

(Answer in terms of $n$)

Improve this question
$\endgroup$
8
$\begingroup$

The weight is always $2 \times n -1$

Explanation

First let's see what the weight of a node is.
The weight of a node is the number of edges that connect to that node except for the root node where it is the number of edges plus 1.
Let's take it one by one to prove.
Proof for non root nodes.
a leaf node has only one edge...the one to the parent. so weight 1.
a node with 1 child has 2 edges. The one to the child and the one to the parent.
a node with 2 children has 3 edges. 2 for the children and one for the parent.
a root node with 2 children has 2 edges and the weight of 3 so edges + 1
a root node with 1 child has 1 edge and weight of 2 so edges +1
a root node with no children (a tree with 1 node) has the weight of 1. so edges + 1.

Now: .

since there are n-1 edges in a tree with n nodes and each edge is counted twice in the tree (once for each node) and since there is only one root node the total weight is $ 2 \times (n - 1) + 1 = 2 \times n - 1$

Extra mile:

Showing that there are n-1 edges in a binary tree.
a tree with 1 node has 0 edges. so this checks out.
a tree with 2 nodes has 1 edge. so it checks out.
a tree with n nodes means adding a new node to a tree with n-1 nodes (which has n-2 edges). Adding one more node means adding one more edge because you have to link the new node to an existing node. So on more node means one more edge.

Improve this answer
$\endgroup$
1
  • 1
    $\begingroup$ You got it exactly right! This is the reasoning I had in mind: rot13(Jura lbh nqq n abqr (nf n yrns), gur cnerag'f inyhr vapernfrf ol 1 naq gur yrns lbh nqq unf n jrvtug bs 1, fb lbh nqq 2 sbe rirel nqqrq abqr. N gerr bs 1 abqr unf n jrvtug bs 1 fvapr vg vf n yrns. Gurersber, gur jrvtug sbe n gerr bs a abqrf vf 2a-1 (2a fvapr vg'f 2 sbe rirel nqqvgvbany abqr, naq -1 gb svg gur onfr pnfr bs jrvtug(a=1) = 1.) $\endgroup$ – DenverCoder1 Aug 13 '20 at 13:25
7
$\begingroup$

The min and max are

both $2n-1$

Proof:

Each node has a base weight of 1, plus 1 extra weight for each child. This means each node contributes 1 extra weight to its parent, except the root which doesn't have a parent. With $n$ nodes, this means total $n$ base weight and $n-1$ total extra weight, for $2n-1$ over all.

Improve this answer
$\endgroup$
2
$\begingroup$

A tree graph $(V,E)$ has the property that the number of edges is one less than the number of vertices ($|E|=|V|-1$). The handshaking lemma also tells you that $2|E|=\sum_{v\in V} d(v)$.

If you

add a single extra node with weight 1 to the root of the tree with one edge, then you get a new graph $(V',E')$ in which the weight of each node is the same as its degree. So the sum of the weights $W$ we are looking for is $$W= -1 + \sum_{v\in V'} W(v) = -1 + \sum_{v\in V'} d(v) = 2|E'|-1 = 2(|V'|-1)-1 = 2n-1$$

Improve this answer
$\endgroup$
2
$\begingroup$

This is just the sum of degrees of a connected tree. The fact that you specified the tree to be binary is only relevant in one aspect; the root node is arbitrarily given an extra weight. A connected tree of $N$ nodes has $N-1$ edges, and the sum of degrees of any graph is always twice the number of edges. So the total weight is $2N-2$, plus the arbitrary extra 1 for the root node, giving a total of $2N-1$.

Improve this answer
$\endgroup$
1
  • $\begingroup$ Good answer. Although, I'm not convinced that the binary nature of the tree factors in at all - you could have an N-ary tree with node weight equal to the number of children + 1, and the result would still come out the same. The extra 1 for the root node comes in because it's the only node where the weight is equal to one more than the node degree, but that's true regardless of how many children each node can have. $\endgroup$ – Nuclear Hoagie Aug 14 '20 at 14:07
2
$\begingroup$

2n - 1 for n >= 1

Reason:

Every node has an initial value of 1 and adds 1 to the value of its parent, except the root node which has no parent which gives the - 1

Improve this answer
$\endgroup$
1
$\begingroup$

To add on to what's already been said, the problem can be generalized for each node having a weight $k + \{\text{# of children}\}$ and for trees that are not binary:

$\text{weight(k,n)} = (k+1)n - 1 = kn+n-1$

The $(k+1)n$ is because every node has a base value of $k$ and every additional child has a value of $1$, so adding a node as a leaf increases the parent's value by $1$ and the leaf's value is $k$.

The weight of any given tree must be $(k+1)n + c$ where $c$ is a constant since we know that every node adds $(k+1)n$ to the weight.

A tree with only 1 node has a value of $k$, so we have $(k+1)1 + c = k$ and therefore $c = -1$.

The fact that a node increases the parent's weight by 1 and adds it's base value does not apply only to binary trees, so this formula will work for ternary trees and n-ary trees as well.

To apply this to the original problem,

Use $k = 1$ to get $\text{weight(n)} = 2n - 1$

Improve this answer
$\endgroup$
0
$\begingroup$

This feels like a homework problem, but the minimum weight would be:

n

Given the case:

n=1, the binary tree would be S the singleton set, so just a leaf with a weight of 1. When n=1 the weight is always 1, so minimum weight is n.

The maximum weight would be:

2n-1

Given the fact that:

Binary trees are recursive, shown in the format of Left, Singleton, Right, so we can break any binary tree down to an n-size of 1 (L and R are empty sets, plus the Singleton set), 2 (Either L or R is an empty set, but not both), or 3 (Neither L nor R are empty sets). From this, when n is 1 we've shown that max weight is n (Which is also 2n-1 for this specific case). When n is 2 it must be a node with a single child, so weight is 2+1=3 (2n-1). When n is 3 it's a node with two children, each are a leaf, so 3+1+1 (also 2n-1).
Due to the recursive nature of Binary Trees, this can be propagated up to any value of n.

Improve this answer
$\endgroup$
5
  • $\begingroup$ For maximum, it is correct, although rot13(gur zvavzhz inyhr vf bayl a va gur pnfr jurer a vf bar. Naq va gung pnfr vg vf nyfb 2a-1.) $\endgroup$ – DenverCoder1 Aug 13 '20 at 13:18
  • 2
    $\begingroup$ The explanation for minimum weight is not really OK. the fact that the numbers check out in your example is just a coincidence. $\endgroup$ – Marius Aug 13 '20 at 13:19
  • $\begingroup$ Using your explanation you can say that the minimum is $\frac{1}{\sqrt{n}}$. It still matches. $\endgroup$ – Marius Aug 13 '20 at 13:34
  • 2
    $\begingroup$ This is not a homework problem, although I understand why you think that. I'm a third year CS student and some first year students taking Data Structures have been asking me for help studying. I felt that some of the problems they had felt much more like puzzles than homework, so I figured I could use it for inspiration. Many problems require more knowledge of DS concepts and I don't think those would belong here, but I felt that if I used only the concept of trees, it would be easily understandable to the community here and fun to some. Thanks for the feedback, though. $\endgroup$ – DenverCoder1 Aug 13 '20 at 13:35
  • 1
    $\begingroup$ Right, I realized as I was writing out the explanation that the value was the same, just unique because of that particular case. Just forgot to change the initial value I stated. $\endgroup$ – Anthony Ingram-Westover Aug 13 '20 at 14:01

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.