Binary Trees

Binary Trees

In the trees, we can have any number of child nodes to a parent node. But if we tout impose some restriction on number of child nodes i.e. if we allow at the most two children nodes then that type of tree is called binary tree. Let us formally define binary trees

Definition of a binary tree:

A binary tree is a finite set of nodes which is either empty or consists of a root and two disjoint binary trees called the left sub‒tree and right sub‒tree.

The binary tree can be as shown below.

Full binary tree

A full binary tree is a tree in which every node has zero or two children.

Complete binary tree

A complete binary tree is full binary tree in which all leaves are at the same depth.

The total number of nodes in complete binary tree are 2^h+1 ‒1 where h is a height of the tree. In above given tree height of tree h is 3. Hence there are

2³⁺¹ −1 = 2⁴ −1 = 15 nodes in the tree.

The number of leaf nodes n in a complete binary tree can be found using formula:

n = 2^h where n is total number of leaf nodes and h is the height of binary tree.

In above given tree h = 3. Hence total 8 nodes (2^h) are leaf nodes.

Left and right skewed trees

The tree in which each node is attached as a left child of parent node then it is left skewed tree. The tree in which each node is attached as a right child of parent node then it is called right skewed tree.

Review Questions

1. Explain the concept of binary trees.

2. Write a short note on ‒ Full binary tree and complete binary tree.