‧͙⁺˚*･༓☾🐺☽༓･*˚⁺‧͙

Binary Tree

2 min read

Non-linear Data Structures

anki

  • Each node can have at-most 2 child nodes.

Node structure of binary tree

Code to create a node

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

Types of binary tree

  • strict / proper binary tree
    • full binary tree
    • 0 or 2 children
  • Complete binary tree
    • all levels except last one are completely filled
    • last level has all keys as much left as possible
  • Perfect binary tree
    • all levels are completely filled
    • all internal nodes have 2 children
    • all leaf nodes are at same level
    • no of leaf nodes= no.of internal nodes + 1
  • Balanced Binary tree
    • height of tree is log n where n is the no of nodes
    • example: AVL trees , Red black trees
      • AVL trees : |height of left subtree - height of right subtree| ⇐1
    • Good performance wise : for search insert and delete
  • Degenerate tree / sparse tree
    • all internal nodes have only a single children
    • if left nodes have single children tree : left skewed
    • if right nodes have single children tree : right skewed

levels and max nodes relation in binary tree

  • levels numbering start from 0
  • max number of nodes on each level = 2^(level)

no of nodes and height relation

n: total no. of nodes in a Binary tree h: height of binary tree

n= 2^0 + 2^1 + 2^2 + 2^3 + ------ + 2

h=log2(n+1)-1 minimum height of the tree

if you are given n nodes then then the level= floor(log2(n)) i.e integer of log2(n)

in general we focus to make a tree complete binary tree so as to maintain the searching complexity to be O(logn) as search space reduces at each level by half

2 methods to implement a binary tree

  • using node struct
  • using arrays ( only for complete binary tree)
    • if the node is stored at ith index
      • the left child gets stored at 2i+1th
      • right child gets stored at 2i+2th

Binary Tree Construction

Graph View