Binary Tree Introduction

BINARY TREE DATA STRUCTURE

              A tree whose elements have at most 2 children is called a binary tree. Since each element in a binary tree can have only 2 children, we typically name them the left and right child.

PARTS OF NODE IN BINARY TREE :

1.      Data,

2.      Pointer to left child, and

3.      Pointer to right child.

THE USED FROM BINARY TREE ARE FOLLOWING :

1.      Manipulate hierarchical data,

2.      Make information easy to search,

3.      Manipulate sort list of data,

4.      Composting digital images for visual effect,

5.      Router Algorithms, and

6.       Form of a multi-stage decision-making (see business chess).

TREE’S PART

1.      Root : The topmost node of the tree. The root always placed on very top of tree.

2.      Children : The element directly under a root. Like the above there said, the tree HAVE the most 2 children. As long they have 2 children, they can be called TREE.

There are a common properties in tree we’ve should known about it. The common properties is the maximum number of nodes at level ‘l’ where ‘l’ is a root of binary tree is . For example, lets take a number for ‘l’ is 1 and we input the 1 into the formula, we can get 2 of the maximum nodes. And the other child below the nodes can be calculate by 2*.

The next common property is maximum number of nodes in a binary tree of height ‘h’ is  . This is a simple geometric series with h terms and sum of this series is 2^h – 1. In some books, height of the root is considered as 0. In this convention, the above formula becomes 2^h+1 – 1.

TYPE OF BINARY TREE

1.      Full Binary Tree 

A Binary Tree is full if every node has 0 or 2 children. Following are examples of a full binary tree. We can also say a full binary tree is a binary tree in which all nodes except leaves have two children.

2.     Complete Binary Tree

A Binary Tree is complete Binary Tree if all levels are completely filled except possibly the last level and the last level has all keys as left as possible

3.     Perfect Binary Tree 

A Binary tree is Perfect Binary Tree in which all internal nodes have two children and all leaves are at the same level.

4.     Balanced Binary Tree

A binary tree is balanced if the height of the tree is O(Log n) where n is the number of nodes. For Example, AVL tree maintains O(Log n) height by making sure that the difference between heights of left and right subtrees is at most 1. Red-Black trees maintain O(Log n) height by making sure that the number of Black nodes on every root to leaf paths are same and there are no adjacent red nodes. Balanced Binary Search trees are performance wise good as they provide O(log n) time for search, insert and delete.

5.     A degenerate (or pathological) tree

 A Tree where every internal node has one child. Such trees are performance-wise same as linked list.

           

            For further information about Binary Tree, there are following source that I take for this document.

            Sources :

https://www.geeksforgeeks.org/binary-tree-data-structure/

https://www.geeksforgeeks.org/binary-tree-data-structure/#Introduction

https://www.geeksforgeeks.org/binary-tree-set-3-types-of-binary-tree/