Binary Tree¶

Each node -> 2 children -> left and right

Representaion¶

A node have:

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

struct node  
{ 
  int data; 
  struct node *left; 
  struct node *right; 
};

Example¶

#include<stdio.h> 
#include<stdlib.h> 
struct node 
{ 
    int data; 
    struct node *left; 
    struct node *right; 
}; 

struct node* newNode(int data) 
{ 

   struct node* node = (struct node*)malloc(sizeof(struct node)); 

   node->data = data; 

   node->left = NULL; 
   node->right = NULL; 
   return(node); 
} 


int main() 
{ 

   struct node *root = newNode(1); 
/* 

    1 
    / \ 
    NULL NULL 
*/

   root->left    = newNode(2); 
   root->right   = newNode(3); 

/* 
    1
    / \ 
    2    3 
    / \ / \ 
    NULL NULL NULL NULL 
*/


   root->left->left = newNode(4); 

/*
        1 
    /    \ 
     2      3 
    / \  / \ 
4 NULL NULL NULL 
    / \ 
  NULL NULL 
*/

   getchar(); 
   return 0; 
} 

Properties¶

Nomenclature

l -> level
h -> height
n -> nodes
L -> Levels

1. max n at l is 2^l
2. max n at h -> 2^h -1 (when root's h = 1) as 1 + 2 + 4 + .. + 2^(h-1) , 2^(h+1) -1 (when root's h = 0)
3. min h in Binary tree = Log2(N+1) reverse of point 2
4. A Binary Tree with L leaves has at least Log2L + 1 levels

 L <=  2^l-1  [From Point 1]
 l =   Log2L + 1 
 where l is the minimum number of levels. 

Full Binary Tree¶

Only 0 or 2 children i.e. only leaf nodes have 0 children.

L = I + 1
Where L = Number of leaf nodes, I = Number of internal nodes

PROOF: https://www.geeksforgeeks.org/handshaking-lemma-and-interesting-tree-properties/

Complete Binary Tree¶

• All levels filled except
• last level -> all nodes are as left as possible

APPLICATION: binary-heap

Perfect Binary Tree¶

• all nodes have 2 children except leaf -> 0
• All levels filled
• n -> 2^h - 1 n with root's h = 1

Balanced Binary Tree¶

• h = log2n
• AVL - h(left sub tree) - h(right sub tree) ≈ 1
• Red-Black trees - Black nodes on every root to leaf paths is the same and there are no adjacent red nodes // TODO don't know
• O(log n) time for search, insert and delete.

A degenerate (or pathological) tree¶

• internal node -> 1 child
• Performance = Linked List

Full¶

            18                                  
           /    \   
         15     20    
        /  \       
      40    50   
    /   \
   30   50

Complete¶

               18
           /       \  
         15         30  
        /  \        /  \
      40    50    100   40
     /  \   /
    8   7  9 

Perfect¶

               18
           /       \  
         15         30  
        /  \        /  \
      40    50    100   40

Balanced¶

// TODO example

Degenerate¶

      10
      /
    20
     \
     30
      \
      40

Applications¶

• Store hierarchical data, like folder structure, organization structure, XML/HTML data.
• Binary Search Tree is a tree that allows fast search, insert, delete on a sorted data. It also allows finding closest item
• Heap is a tree data structure which is implemented using arrays and used to implement priority queues. B-Tree and B+ Tree : They are used to implement indexing in databases. Syntax Tree: Used in Compilers. K-D Tree: A space partitioning tree used to organize points in K dimensional space. Trie : Used to implement dictionaries with prefix lookup. Suffix Tree : For quick pattern searching in a fixed text. Spanning Trees and shortest path trees are used in routers and bridges respectively in computer networks As a workflow for compositing digital images for visual effects.