1

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.

Community
  • 1
  • 1
randomUser47534
  • 329
  • 1
  • 5
  • 18

2 Answers2

1

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):

    *
   / \
  *   *
 /
*
Aasmund Eldhuset
  • 37,289
  • 4
  • 68
  • 81
  • Ok, thanks! To clarify, if a tree is balanced, then it's height is as small as possible (i.e. you could not rearrange the nodes to achieve an even smaller height)? So, to amend my earlier definition: a binary tree is balanced iff the number of edges on every root-to-leaf path differs by at most one and the height is as small as possible? – randomUser47534 Mar 29 '15 at 00:40
  • Correct. However, "as small as possible" would need to be defined in terms of how many nodes you can fit in a tree with a given arity and height, and for arities other than 2, the expressions become tricky. So I find it more convenient to think about the levels of the tree (a level is all the nodes that could potentially exist at a given distance from the root), and only allowing the last one to be non-full. – Aasmund Eldhuset Mar 29 '15 at 00:52
  • Also, note that in other contexts, there may be different notions of balancedness. For example, when discussing balanced search trees, it is sufficient that the deepest leaf is at most twice as deep as the shallowest leaf. – Aasmund Eldhuset Mar 29 '15 at 00:54
0

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!

richerlariviere
  • 799
  • 2
  • 13
  • 29