Binary Tree Introduction

By | January 17, 2016

Introduction to Binary Tree

Binary Tree IntroductionTrees are hierarchical data structures.

The topmost node is called root of the tree.
The elements that are directly under an element are called its children. The element directly above something is called its parent.
Elements with no children are called leaf nodes or leaves.

A tree whose elements have at most 2 children is called a binary tree. Conventionally, we call them left and right child.

 

Rbinary tree exampleoot Node: 50
Leaf Nodes: 12, 19, 67
17 is left child of 50, and parent to 9 and 23
Similarly, 76 is right child of 50 and parent to 54

Binary Tree Introduction Video Explanation:

Need for Trees:

  1. To store information that naturally forms a hierarchy and uses categorization.
    Example: File Systems, Family Trees.
  2. Trees (with some ordering such as BST) provide access and search operations quicker than Linked List.
  3. Trees provide insertion and deletion operations quicker than arrays but slower than Unordered Linked Lists.
  4. Like Linked Lists, trees are dynamic and don’t have an upper limit on number of nodes.

Self balancing search trees like AVL and Red-Black trees guarantee an upper bound of O(Logn) for search, insertion and deletion.

Main applications of trees include:

  1. Manipulate hierarchical data.
  2. Make information easy to search.
  3. Manipulate sorted lists of data.
  4. As a workflow for compositing digital images for visual effects.
  5. Router algorithms.
  6. Form of a multi-stage decision-making.

Binary Tree Representation in C/C++

We represent a binary tree node using self-referential structures (structure having pointer(s) to itself). It contains the following members:

  1. Data.
  2. Pointer to left child.
  3. Pointer to right child.

We maintain a pointer to the root node of the tree. If the tree is empty, then value of root is NULL.

We can also represent a binary tree using arrays.
Root lies at index 0.
Parent of index i is at index: ceil(i/2) – 1.
Left Child of index i is at index: 2i + 1.
Right Child of index i is at index: 2i + 2.
Example:

Although this representation will result in space wastage when our tree is not a complete or perfect binary tree.
This representation is also not dynamic as we will need to declare array size in the program itself.