Home Theory The basics of Binary Trees

The basics of Binary Trees

by nikoo28
0 comment 3 minutes read

A tree is called a binary tree if each node has zero child, one child or two children. Empty tree is also a valid binary tree. We can visualize a binary tree as consisting of a root and two disjoint binary trees, called the left and right sub-trees of the root.

Generic Binary Tree

binary_tree

Types of Binary Trees

Strict Binary Tree:

A tree is called a strict binary tree if each node has exactly two children or no children.

binary_tree_1

Full Binary Tree:

A binary tree is called a full binary tree if each node has exactly two children and all leaf nodes are at the same level.

binary_tree_2

Complete Binary Tree:

Before defining the complete binary tree, let us assume that the height of the binary tree is h. In complete binary trees, if we give numbering for the nodes by starting at root (let us say the root node has 1) then we get a complete sequence from 1 to number of nodes in the tree.While traversing we should give numbering for NULL pointers also. A binary tree is called a complete binary tree if all leaf nodes are at height h or h-1 and also without any missing number in the sequence.

binary_tree_3

Properties of Binary Trees

For the following properties, let us assume that the height of the tree is h. Also, assume that root node is at height zero. From the diagram shown below we can infer the following properties.

  • The number of nodes ‘n’ in a full binary tree is 2h+1 – 1. Since, there are h levels we need to add all nodes at each level [20 + 21 + 22 + ….. + 2h = 2h+1 – 1]
  • The number if nodes n in a complete binary tree is between 2h (minimum) and 2h+1 – 1 (maximum).
  • The number of leaf nodes in a full binary tree are 2h.
  • The number of NULL links (wasted pointers) in a complete binary tree of n nodes are n+1.

binary_tree_4

You may also like

This website uses cookies to improve your experience. We'll assume you're ok with this, but you can opt-out if you wish. Accept Read More