CODEWITHSUNDEEP
binary-tree
user1424934
user1424934

Reputation: 153

Binary Tree Definition

I see this definition of a binary tree in Wikipedia:

Another way of defining binary trees is a recursive definition on directed graphs. A binary tree is either:

A single vertex.

A graph formed by taking two binary trees, adding a vertex, and adding an edge directed from the new vertex to the root of each binary tree.

How then is it possible to have a binary tree with one root and one left son, like this:

         O
        /
       O

This is a binary tree, right? What am I missing here?

And please don't just say "Wikipedia can be wrong", I've seen this definition in a few other places as well.

Upvotes: 0

Views: 439

Answers (3)

amdn
amdn

Reputation: 11582

Wikipedia can be wrong. Binary trees are finite data structures, a subtree must be allowed to be empty otherwise binary trees would be infinite. The base case for the recursive definition of a binary tree must allow either a single node or the empty tree.

Section 14.4 of Touch of Class: An Introduction to Programming Well Using Objects and Contracts, by Bertrand Meyer, Springer Verlag, 2009. © Bertrand Meyer, 2009. has a better recursive definition of a binary tree

Definition: binary tree

A binary tree over G, for an arbitrary data type G, is a finite set of items called
nodes, each containing a value of type G, such that the nodes, if any, are
divided into three disjoint parts:
  • A single node, called the root of the binary tree.
  • (Recursively) two binary trees over G, called the  left subtree and right subtree.

The definition explicitly allows a binary tree to be empty (“the nodes, if any”).
Without this, of course, the recursive definition would lead to an infinite
structure, whereas our binary trees are, as the definition also prescribes, finite.
If not empty, a binary tree always has a root, and may have: no subtree; a
left subtree only; a right subtree only; or both.

Upvotes: 0

Grzegorz
Grzegorz

Reputation: 3335

Correct. A tree can be empty (nil)

Let's assume you have two trees: one, that has one vertex, and one which is empty (nil). They look like this:

O   .

Notice that I used a dot for the (nil) tree.

Then I add a new vertex, and edges from the new vertex to the existing two trees (notice that we do not take edges from the existing trees and connect them to the new vertes - it would be impossible.). So it looks like it now:

   O
  / \
 O   .

Since edges leading to (nil) are not drawn, here it is what is at the end:

   O
  /
 O

I hope it clarifies.

Upvotes: 2

Parallelis
Parallelis

Reputation: 719

It depends on the algorithm you use for binary-tree: as for icecream, there are many flavors :)

One example is when you have a mix of node pointers and leaf pointers on a node, and a balancing system that decide to create a second node (wether it's the root or the other) when you are inserting new values on a full node: instead of creating a root and 2 leafs, by splitting it, it's much more economical to create just another node.

Upvotes: 0

Related Questions