Data Strucrures



  Template for SLL   Singly Linked List   Stack Using Linked List   Operations on Linked List   Queue Using Linked List   Double Linked List   Polynomial using Linked List   Generalize Linked List
  Tree Terminologies   Binary Tree   Binary Tree Traversals   Binary Search Tree Traversals   Binary Search Tree Operations
  Introduction   Graph Traversals   Minimum Spanning Tree   Graph Representation
  Hash Table Operations


Binary Tree

   Linear Search and Binary Search PPT
Prev Post
Next Post

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

Properties of Binary Tree

1. For Binary Tree, maximum number of nodes at level L are 2L

2. A full Binary tree of height ‘h’ has ( 2h + 1 – 1 ) total nodes

3. Total number of external nodes in a binary tree are internal nodes + 1. i.e. e = i + 1

Types of Binary Tree

1. Skew Binary Tree

2. Complete Binary Tree

3. Full Binary Tree

1. Skew Binary Tree

Every node is having either only left or right subtree

2. Complete Binary Tree

All Leaves  are at the same depth / level

3. Full Binary Tree

every node has zero or two children. Also called Strictly B.T.

Representation of Binary Tree

1. Sequential Representation

Followings are the rules for sequential representation

Rules:

  • Parent ( i ) = floor(i-1)/2
  • Leftchild ( i ) = (2i+1)
  • Rightchild( i )= (2i + 2)

2. Linked Representation

 

Converting General Tree to Binary Tree

Any general tree can be represented as binary tree using following algorithm:

  1. All nodes of general tree will be nodes of binary tree
  2. The root T’ of general tree is the root of binary tree T.
  3. To obtain a binary tree, we use a relationship b/w the nodes that can be characterized by two characteristics:
  4. a) One relationship is the “leftmost-child-next-right-sibling relationship”.
  5. b) Every node has at most one leftmost child and at most one next right sibling.

Use following steps to obtain T’ from T:

  1. Connect (insert an arrow from) each node to its right sibling (if one exists).
  2. Disconnect (remove arrow from) each node from (to) all but not the leftmost child.

Example

Convert the following general Tree to BInary Tree

Following steps can be used to convert above general tree to Binary Tree

1. First, connect all siblings with new link

In above step, we have connected all siblings with new link i.e. at first level, 2,5 and 7 are the siblings, therefore at Level 1, these siblings have been connected with new link and also at Level-2, 2 and 4, 8,9,and 10 are the siblings, therefore all these siblings have been connected with new link which is shown in above figure.

2. Disconnect all original links except leftmost link

Here, we have disconnected all original links ( Not the links which we created newly) except leftmost link. In above figure, 1-2, 2-3, 5-6 and 7-8 are the leftmost original links. Except these original links, disconnect all other original links which is shown in above figure.

Therfore final converted Binary tree is