According to a previous StackOverflow answer, a binary tree is balanced iff the heights of its two subtrees never differ by more than one (Complete binary tree definitions).
Is this the same as saying: a binary tree is balanced iff the number of edges on every root-to-leaf path at most differs by one?
I'm trying to visualize what a binary tree vs. a non-binary tree looks like, and am struggling with wrapping my head around the concept.
Thanks.
Almost, except if one of the subtrees are empty:
*
\
*
\
*
The definition you cite is a little problematic because an empty tree doesn't really have a height, but it works if you define empty trees to have height -1. The above tree is unbalanced, since the (empty) left subtree has height -1 and the right subtree has height 1. However, your definition would declare the tree to be balanced: there's only one root-to-leaf path, so there can't be any mismatch with other such paths.
However, balancedness is only partially related to binary-ness. Being binary simply means that no node has more than two children. Here's an example of a non-binary tree that is balanced:
*
/|\
* * *
However, the arity (the limit on the number of child nodes) of a tree can affect its balancedness. The following tree is balanced if you declare it to be binary (there are only two subtrees, of height 1 and 0), and unbalanced if you declare it to be ternary (there is a middle subtree of the root, and it is empty):
*
/ \
* *
/
*
A binary tree should only have a maximum of two childrens per node. I found a site which show different data structures (you can play with them they are animated).
If you are interested about self-balancing trees, check out AVL tree, you will understand why a binary tree can be unbalanced. Good luck!
