A binary tree is a tree data structure in which each node has at most two children, which are referred to as the left child and the right child.

https://upload.wikimedia.org/wikipedia/commons/thumb/f/f7/Binary_tree.svg/300px-Binary_tree.svg.png

It is implemented mainly using Links.

Binary Tree Representation:

 A tree is represented by a pointer to the topmost node in the tree. If the tree is empty, then the value of root is NULL. A Binary Tree node contains following parts.

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

A Binary Tree can be traversed in two ways:

  • Depth First Traversal: It is stack implementation. A Left-first walk around a tree starts at the root and walks alongside the edges keeping the edges always on the left, until returning to the root after visiting all the edges.
    • Inorder Traversal (Left-Root-Right) - Record each leaf as soon as you see it and each internal vertex the second time you see it.
      • Push root onto stack
      • While stack is not empty
        • v := top(stack)
        • While v has a left-child
          • Push leftchild(v) onto stack
          • v:= leftchild(v)
        • v := pop(stack)
        • List v
        • If v has a right-child
          • Push rightchild(v) onto stack
          • v := rightchild(v)
        • Else
          • While stack not empty and v has no right-child
            • v := pop(stack)
            • List v
          • If v has a right-child
            • Push rightchild(v) onto stack
            • v := rightchild(v)
    • Preorder Traversal (Root-Left-Right) - Record each vertex the first time it is seen (and not again).
      • Push root onto stack.
      • While stack is not empty:
        • Pop a vertex off stack, and write it on output list.
        • Push its children, right to left onto stack.
    • Postorder Traversal (Left-Right-Root) - Record each vertex the last time it is seen (and not before).
      • Push root onto stack
      • While stack is not empty
        • If top(stack) is unmarked, mark it and push its children right to left onto stack,
        • Else, pop stack to output list.
  • Breadth First Traversal: It is Queue implementation.
    • Level Order Traversal - The level-order of an ordered tree is a listing of the vertices in increasing order of depth, such that the vertices of equal depth are listed according to their prescribed order.
      • Enqueue root.
      • While queue is not empty:
        • Dequeue a vertex and write it on the output list.
        • Enqueue its children left to right.

Binary Tree Properties:

  • The maximum number of nodes at level ‘l’ = 2l-1.
  • A maximum number of nodes with height 'h'= 2h – 1
    • Height is considered as is the maximum number of nodes on the root to leaf path
  • Minimum possible height =  ceil(Log2(n+1))   
  • A number of leaf nodes are always one more than nodes with two children.

Examples:

  • Decision tree with Yes/No action

 

 

Time Complexity

Space Complexity

 

Average

Worst

Worst

Data Structure 

 Access 
 Search 
 Insertion 
 Deletion 
 Access 
 Search 
 Insertion 
 Deletion 
 

Binary Search Tree

Θ(log(n)) Θ(log(n)) Θ(log(n)) Θ(log(n)) O(n) O(n) O(n) O(n) O(n)

Cartesian Tree

N/A Θ(log(n)) Θ(log(n)) Θ(log(n)) N/A O(n)  O(n)  O(n)  O(n)

B-Tree

Θ(log(n)) Θ(log(n)) Θ(log(n)) Θ(log(n)) O(log(n)) O(log(n)) O(log(n)) O(log(n)) O(n)

Red-Black Tree

Θ(log(n)) Θ(log(n)) Θ(log(n)) Θ(log(n)) O(log(n)) O(log(n)) O(log(n)) O(log(n)) O(n)

Splay Tree

N/A Θ(log(n)) Θ(log(n)) Θ(log(n)) N/A O(log(n)) O(log(n)) O(log(n)) O(n)

AVL Tree

Θ(log(n)) Θ(log(n)) Θ(log(n)) Θ(log(n)) O(log(n)) O(log(n)) O(log(n)) O(log(n)) O(n)

KD Tree

Θ(log(n)) Θ(log(n)) Θ(log(n)) Θ(log(n)) O(n) O(n) O(n) O(n) O(n)

Binary Search Tree

BST (Binary Search Tree) is ordered Binary Tree.

In Binary Search Tree is a Binary Tree with following additional properties:

  1. The left subtree of a node contains only nodes with keys less than the node’s key.
  2. The right subtree of a node contains only nodes with keys greater than the node’s key.
  3. The left and right subtree each must also be a binary search tree.

https://upload.wikimedia.org/wikipedia/commons/thumb/d/da/Binary_search_tree.svg/300px-Binary_search_tree.svg.png

Each of whose vertices is assigned a key, such that the key assigned to any vertex v is greater than the key at each vertex of the left subtree at v and less than the key at any vertex of the right subtree of v.

Time Complexities:

  • Search:  O(h)
  • Insertion: O(h)
  • Deletion: O(h)
  • Extra Space: O(n) for pointers
  • h: Height of BST
  • n: Number of nodes in BST

If Binary Search Tree is Height Balanced, then h = O(Log n) 

Self-Balancing BSTs such as AVL Tree, Red-Black Tree, and Splay Tree make sure that height of BST remains O(Log n).


BST provide moderate access/search (quicker than Linked List and slower than arrays).
BST provide moderate insertion/deletion (quicker than Arrays and slower than Linked Lists).

Example:

  • Product sorting in e-commerce site
  • Groping or sorting video files on Youtube, Netflix

 

 

Time Complexity

Space Complexity

 

Average

Worst

Worst

Data Structure 

 Access 
 Search 
 Insertion 
 Deletion 
 Access 
 Search 
 Insertion 
 Deletion 
 

Binary Search Tree

Θ(log(n)) Θ(log(n)) Θ(log(n)) Θ(log(n)) O(n) O(n) O(n) O(n) O(n)

Complete Binary Tree

A binary tree is a call as 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.

http://web.cecs.pdx.edu/~sheard/course/Cs163/Graphics/CompleteBinary.jpg

Example:

 

 

Time Complexity

Space Complexity

 

Average

Worst

Worst

Data Structure 

 Access 
 Search 
 Insertion 
 Deletion 
 Access 
 Search 
 Insertion 
 Deletion 
 

Binary Search Tree

Θ(log(n)) Θ(log(n)) Θ(log(n)) Θ(log(n)) O(n) O(n) O(n) O(n) O(n)

Cartesian Tree

N/A Θ(log(n)) Θ(log(n)) Θ(log(n)) N/A O(n)  O(n)  O(n)  O(n)

B-Tree

Θ(log(n)) Θ(log(n)) Θ(log(n)) Θ(log(n)) O(log(n)) O(log(n)) O(log(n)) O(log(n)) O(n)

Red-Black Tree

Θ(log(n)) Θ(log(n)) Θ(log(n)) Θ(log(n)) O(log(n)) O(log(n)) O(log(n)) O(log(n)) O(n)

Splay Tree

N/A Θ(log(n)) Θ(log(n)) Θ(log(n)) N/A O(log(n)) O(log(n)) O(log(n)) O(n)

AVL Tree

Θ(log(n)) Θ(log(n)) Θ(log(n)) Θ(log(n)) O(log(n)) O(log(n)) O(log(n)) O(log(n)) O(n)

KD Tree

Θ(log(n)) Θ(log(n)) Θ(log(n)) Θ(log(n)) O(n) O(n) O(n) O(n) O(n)

Full Binary Tree - Non-Linear Data Structures

A binary tree is full if every node has 0 or 2 children.‚Äč

In a Full Binary, a number of leaf nodes are a number of internal nodes plus 1. 

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

 

In a k-ary tree where every node has either 0 or k children.

L = (k - 1)*I + 1 Where L = Number of leaf nodes,  I = Number of internal nodes 

 

 

Time Complexity

Space Complexity

 

Average

Worst

Worst

Data Structure 

 Access 
 Search 
 Insertion 
 Deletion 
 Access 
 Search 
 Insertion 
 Deletion 
 

Binary Search Tree

Θ(log(n)) Θ(log(n)) Θ(log(n)) Θ(log(n)) O(n) O(n) O(n) O(n) O(n)

Cartesian Tree

N/A Θ(log(n)) Θ(log(n)) Θ(log(n)) N/A O(n)  O(n)  O(n)  O(n)

B-Tree

Θ(log(n)) Θ(log(n)) Θ(log(n)) Θ(log(n)) O(log(n)) O(log(n)) O(log(n)) O(log(n)) O(n)

Red-Black Tree

Θ(log(n)) Θ(log(n)) Θ(log(n)) Θ(log(n)) O(log(n)) O(log(n)) O(log(n)) O(log(n)) O(n)

Splay Tree

N/A Θ(log(n)) Θ(log(n)) Θ(log(n)) N/A O(log(n)) O(log(n)) O(log(n)) O(n)

AVL Tree

Θ(log(n)) Θ(log(n)) Θ(log(n)) Θ(log(n)) O(log(n)) O(log(n)) O(log(n)) O(log(n)) O(n)

KD Tree

Θ(log(n)) Θ(log(n)) Θ(log(n)) Θ(log(n)) O(n) O(n) O(n) O(n) O(n)

Perfect Binary Tree - Non-Linear Data Structures

A binary tree is Perfect if all internal nodes have two children and all leaves are at same level.

Examples:

  • Family tree

 

 

 

Time Complexity

Space Complexity

 

Average

Worst

Worst

Data Structure 

 Access 
 Search 
 Insertion 
 Deletion 
 Access 
 Search 
 Insertion 
 Deletion 
 

Binary Search Tree

Θ(log(n)) Θ(log(n)) Θ(log(n)) Θ(log(n)) O(n) O(n) O(n) O(n) O(n)

Cartesian Tree

N/A Θ(log(n)) Θ(log(n)) Θ(log(n)) N/A O(n)  O(n)  O(n)  O(n)

B-Tree

Θ(log(n)) Θ(log(n)) Θ(log(n)) Θ(log(n)) O(log(n)) O(log(n)) O(log(n)) O(log(n)) O(n)

Red-Black Tree

Θ(log(n)) Θ(log(n)) Θ(log(n)) Θ(log(n)) O(log(n)) O(log(n)) O(log(n)) O(log(n)) O(n)

Splay Tree

N/A Θ(log(n)) Θ(log(n)) Θ(log(n)) N/A O(log(n)) O(log(n)) O(log(n)) O(n)

AVL Tree

Θ(log(n)) Θ(log(n)) Θ(log(n)) Θ(log(n)) O(log(n)) O(log(n)) O(log(n)) O(log(n)) O(n)

KD Tree

Θ(log(n)) Θ(log(n)) Θ(log(n)) Θ(log(n)) O(n) O(n) O(n) O(n) O(n)

Balanced Binary Tree - Non-Linear Data Structures

A binary tree is Balanced if height of the tree is O(Log n) where n is number of nodes.

Balanced Binary Search trees are performance wise good as they provide O(log n) time for search, insert and delete.

binary tree is balanced if, for every vertex, the number of vertices in its left and right subtrees differs by at most one.

Examples:

  • AVL Tree
  • Red-Black trees

 

 

 

Time Complexity

Space Complexity

 

Average

Worst

Worst

Data Structure 

 Access 
 Search 
 Insertion 
 Deletion 
 Access 
 Search 
 Insertion 
 Deletion 
 

Red-Black Tree

Θ(log(n)) Θ(log(n)) Θ(log(n)) Θ(log(n)) O(log(n)) O(log(n)) O(log(n)) O(log(n)) O(n)

AVL Tree

Θ(log(n)) Θ(log(n)) Θ(log(n)) Θ(log(n)) O(log(n)) O(log(n)) O(log(n)) O(log(n)) O(n)