Binary Trees

In a normal tree, each node can have any number of children. A Binary tree is a special case of general tree in which every node can have a maximum of two children. One is known as the left child and the other as right child.

Properties of the binary tree

1. The maximum number of nodes at level l of a binary tree is 2l-1.
2. The maximum number of nodes in a binary tree of height h is 2h – 1.
3. In a binary tree with N nodes, minimum possible height or minimum number of levels is ⌈log (N+1)⌉ (ceiling function and log with base 2)
4. A Binary Tree with L leaves has at least ⌈ log L ⌉ + 1 (ceiling function and log with base 2) levels.

Representation of a binary tree

A binary tree data structure can be represented using two methods:

Array Representation

The binary tree is stored in a 1-D array. The root is given the 0th index in the tree. The nodes are then numbered from the left to right going from the top to bottom. Empty elements are also stored in this array.

Each node is then put in the array with respect to its index in the tree.

Linked List Representation

A linked list may be used to store a binary tree. Each Node of the list would consist of 3 fields: The data of the element, a pointer to the left child and a pointer to the right child.

A leaf node will have both the left and right pointers to a NULL value signifying the end of the tree.

Types of binary trees

1. Strictly Binary Tree

A binary tree in which every node has either zero or two children. In other words, the degree of each node of the tree is either zero or two.

2. Complete Binary Tree

A binary tree in which every internal node has exactly two children and all leaf nodes are at the same level.

3. Extended Binary Tree

An extended binary tree is made by replacing all the NULL subtrees with dummy nodes. The resulting tree is a Complete Binary Tree where every node has exactly two children and every external node is a leaf.

Thus, the binary tree obtained by adding dummy nodes to a binary tree is called Extended Binary Tree.

4. Threaded Binary Tree

In a threaded Binary Tree, all the left child pointers that are NULL points to its in-order predecessor, and all right child pointers that are NULL points to its in-order successor, if they exist.

The idea is to make in-order traversal faster in the tree without implementing any other data structure.

There can be 2 variations of a threaded binary tree:

Single-Threaded Binary Tree

Only the right NULL pointer is made to point to the in-order successor if it exists.

Double-Threaded Binary Tree

Both the left and right NULL pointers are made to point to the in-order predecessor and in-order successor respectively. The two links make it useful for both reverse in-order and post-order traversal.

Videos

• Binary tree | mycodeschool: Excellent explanation from mycodeschool