Is smallest binary tree simply root node? Or does it need to have two child nodes?

Question

Apologies for this rather simplistic question, I've just started looking at binary trees and the material I've been provided wasn't explicit about this.

Presumably a parent node of a binary tree can have 1 child node but not more than 2?

I'm looking at proofs on binary trees using well founded induction and would like to check my understanding of a binary tree in relation to R-minimal elements.

Additionally, how might I state with proper mathematical notation that it is a well founded relation rather than explain why it is.

Thank you!

Answer 1

There are three main conventions regarding rooted binary trees:

1. The node can have 0, 1 or 2 sons with no distinction between left and right (with leafs being a node without children). The root only is a proper tree.
2. The node can have one left child and one right child (total number is 0, 1 or 2, leafs defined as in 1.). The root only is a proper tree.
3. The node always have 2 sons, but there are special placeholders that have always 0 nodes (and here those are called leafs). It varies, usually it follows from the context if the tree can be "empty" or not.

Whatever the convention is, parent node never has more than 2 children (therefore binary tree).

In a case of a finite tree, well-founded induction follows usually from the root to the leaves, but other directions (e.g. from the leaves to the root) are also possible. Also, it is helpful to know that one can reroot the tree (in case of convention 1 or 2) -- you just grab one of the vertices and keeping the tree in the air shake it a little, so all the other nodes will fall below the one you have in the hand (remember, do not shake it to much or the branches may snap...).

To proof that relation is well-founded you need to show that it doesn't contain infinite descending chains. There are many techniques that can be used, but the easiest (this is my opinion only) is to inject it into another relation such that you know it is well-founded, i.e. to proof that $R$ is well-founded it is enough to show that there exists some well-founded $S$ and a map $f : R \to S$ such that $a < b \Rightarrow f(a) < f(b)$ (notice the strict inequality!). Useful examples of $S$ are:

• natural numbers;
• lexicographic order on tuples of fixed length (each element of the tuple may be compared using different order as long as all the orders are well-founded);
• lexicographic order on tuples of any length with it's length (as a natural number with standard ordering) at the first place;
• multiset order (this one is really nice);
• any DAGs (directed acyclic graphs), e.g. other trees;
• any other well-founded relation that you know.

Finally, beware the non-strict inequalities, usually they only cause troubles in this context!

Edit: I couldn't find any nice papers that define the usual multiset ordering (by Dershowitz and Manna), so here is the definition:

Let $\mathbb{X}$ be any set and $M$ and $N$ be two multisets on $\mathbb{X}$, that means functions $\mathbb{X}\to\mathbb{N}$ with finite support. Then $M <_{DM} N$ if and only if there exist two multisets $A$ and $B$ such that

• $\varnothing \neq A, A \subseteq N$,
• $M = (N - A) + B$,
• $\forall b \in B\ \ \exists a \in A.\ b <_\mathbb{X} a$.

Intuitively it means that you can exchange one element from $N$ to any number of strictly smaller (with respect to some ordering $<_\mathbb{X}$ on $\mathbb{X}$ ) elements in $M$.

There is also equivalent definition that reads $M <_{DM} N$ if and only if they are not equal and $$\forall x \in \mathbb{X}.\ N(x) <_\mathbb{N} M(x) \Rightarrow \exists y \in \mathbb{X}.\ x <_\mathbb{X} y \land M(y) <_\mathbb{N} N(y).$$

Maybe even that one is easier too understand.

Hope that helps ;-)