# What is a balanced tree? [closed]

I was going through a handout. It had the text (p.4):

Let $$G$$ be a tree and $$v$$ be any vertex of $$G$$. Let $$v_1,v_2,v_3,\dots, v_t$$ be vertices adjacent to $$v$$. Let $$e_i$$ be the edge joining $$v$$ and $$v_i$$. Let $$T_i$$ be subtree containing $$v_i$$ after removing edge $$e_i$$. Let $$f(v)= \max_{i=1}^t |V(T_i)|$$.

Since $$\sum |V(T_i)|=n-1$$, if $$f(v)$$ is large, then the tree looks unbalanced. If $$f(v) \approx (n-1)/t$$ then the tree looks balanced.

however it didn't explain what a balanced graph is. What is a balanced tree?

• Have you tried searching for "balanced tree" with your favorite search engine? – John Douma Apr 12 at 12:12
• @JohnDouma It wouldn't really help, in this case. – Misha Lavrov Apr 12 at 12:23

Instead, the word "balancing" is being used for intuition, and the intuition you should have is this. If $$v$$ is a vertex in an $$n$$-vertex tree $$T$$ with $$\deg(v)=t$$, then deleting $$v$$ from $$T$$ leaves a forest $$T-v$$ with $$t$$ components. (Each of $$v$$'s former neighbors is now in a different component of $$T-v$$.)
If there are $$n$$ vertices in $$T$$, there are $$n-1$$ in $$T-v$$, so the average order of a component is $$\frac{n-1}{t}$$. We defined $$f(v)$$ to be the maximum order of any component. Thus:
• If $$f(v) \approx \frac{n-1}{t}$$, then the largest component of $$T-v$$ is approximately average, which means all components must be approximately average. They are "balanced" in that each one has about the same number of vertices.
• If $$f(v)$$ is much larger than $$\frac{n-1}{t}$$, then the largest component of $$T-v$$ is much larger than average. The components are unbalanced: one has many more vertices than the others.
Often we split a tree by deleting an edge, and we would like the two resulting components to be as equal as possible. If we delete an edge $$vv_i$$, then one component of $$T-vv_i$$ is the component of $$T-v$$ containing $$v_i$$, and the other component is everything else. The best thing we can do is delete the edge to the largest component of $$T-v$$: in that case, one component has $$f(v)$$ vertices, and the other has $$n - f(v)$$.
Relatedly, for the "tree balancing exercise" on the next page of the hand out, see this post for why the upper bound on $$\min_v f(v)$$ isn't very good, and could be significantly improved. (To be fair, all we need is a lower bound on the smaller of $$f(v)$$ and $$n-f(v)$$, and $$f(v)$$ is usually the bottleneck there.)