Binary Tress - Types and Properties

 

๐ŸŒณ What is a Binary Tree?

A binary tree is a special type of tree where each node has at most two children:

  • Left child

  • Right child

✅ It is hierarchical and recursive in nature.


๐Ÿ”ฅ Types of Binary Trees

There are several special types of binary trees based on structure:

1. Full Binary Tree

  • Every node has 0 or 2 children. (No node with only 1 child)


2. Perfect Binary Tree

  • It is a full binary tree where all leaf nodes are at the same level.


3. Complete Binary Tree

  • All levels are completely filled except possibly the last level, which is filled from left to right.


4. Balanced Binary Tree

  • The height difference between left and right subtree for every node is at most 1.

Examples: AVL Tree, Red-Black Tree.

5. Degenerate (or Skewed) Tree

  • Every parent has only one child.

Two types:

  • Left-skewed tree (only left child)

  • Right-skewed tree (only right child)



๐Ÿ”ต Summary Table

Type of TreeKey Characteristics
Full Binary Tree                0 or 2 children only
Perfect Binary Tree                Full + all leaves at same level
Complete Binary Tree                All levels full except last, filled left to right
Balanced Binary Tree                Height balanced
Degenerate Tree                Like a linked list

๐ŸŒŸ Important Properties of Binary Trees

1. Maximum number of nodes at level i

At level i (root is level 0), the maximum number of nodes = 2แถฆ.

Example:
Level 0 → 1 node
Level 1 → 2 nodes
Level 2 → 4 nodes
Level 3 → 8 nodes, and so on.

2. Maximum number of nodes in a binary tree of height h

Maximum nodes = 2^(h+1) - 1

where h = height of the tree (root is height 0).

Example:
Height 2 → Maximum 2³ - 1 = 7 nodes.

3. Minimum possible height (h) of a binary tree with n nodes

Minimum height = ⌈log₂(n+1)⌉ - 1

where ⌈ ⌉ is the ceiling function (round up).

Example:
If n = 7 nodes → height = ⌈log₂(8)⌉ - 1 = 3 - 1 = 2

4. In a perfect binary tree:

  • Number of leaf nodes = (number of internal nodes) + 1

  • Total nodes = 2 × (number of leaf nodes) - 1

Example:
3 leaf nodes → Total nodes = 2×3 -1 = 5 nodes.

5. Relationship between number of leaf nodes (L) and total nodes (N)

In a full binary tree:

  • L = (N + 1) / 2

  • Internal nodes = (N - 1) / 2

Example:
N = 7 →
L = (7+1)/2 = 4 leaves,
Internal = (7-1)/2 = 3 internal nodes.

6. A binary tree with n nodes has exactly n-1 edges

Each node (except root) connects to its parent by one edge.

7. Traversals (important algorithms)

  • Inorder (Left, Root, Right) — used for BST sorted order.

  • Preorder (Root, Left, Right) — used to create a copy of the tree.

  • Postorder (Left, Right, Root) — used to delete the tree.

8. Types of binary trees

  • Full Binary Tree

  • Perfect Binary Tree

  • Complete Binary Tree

  • Balanced Binary Tree

  • Degenerate Tree

Each has specific structural properties (which we already discussed earlier).

๐Ÿ”ต Quick Summary Table

PropertyFormula
Max nodes at level i            2แถฆ
Max total nodes of height h        2^(h+1) - 1
Min height with n nodes        ⌈log₂(n+1)⌉ - 1
Leaf nodes in perfect tree        Internal nodes + 1
Edges in binary tree        n - 1

Comments

Post a Comment

Popular posts from this blog

Data Structures and Algorithms PCCST303 KTU 2024 Scheme- Dr Binu V P

About Me Syllabus and evaluation scheme  1.Basic Concepts of Data Structures     Data structures and data abstraction     Time and Space Complexity     Asymptotic Analysis and Asymptotic Notations     Best case, Worst case and Average Case Analysis of Algorithms     Frequency Count Method of Algorithm Analysis     Polynomial Representation using arrays      Polynomial Addition using arrays      Sparse Addition and Transpose     Stacks     Multi Stacks      Queue using array      Circular Queue using array      Double ended Queue using array     Infix to postfix and postfix evaluation     Infix to prefix and prefix evaluation    2.Linked List and Memory Management          Self Referential Data Structures     Dynamic Memory Allocation in C     Singly Linked...
Read more

Performance Analysis - Time and Space Complexity

Image
  ๐Ÿ“š Performance Analysis  Performance analysis means studying how efficient an algorithm or data structure is. Mainly, we check two things: Time Complexity — How much time (number of operations) the algorithm takes. Space Complexity — How much memory (space) the algorithm uses. ✅ Goal : To predict how the algorithm will behave as the input size grows without running the code. ๐Ÿ“ 1. Time Complexity Measures the amount of time an algorithm takes to complete. It is expressed as a function of the input size n . We usually use Big-O notation (e.g., O(n), O(log n), O(n²)) to express it. ⏳ Why it matters? Because we want algorithms that are fast even for large inputs . Example for Time Complexity: Suppose we have a simple loop: for ( int i = 0 ; i < n; i++) { printf ( "%d " , i); } The loop runs n times . Each printf is a constant-time operation. So, Time Complexity = O(n) (linear time). Types of Common Time Complexities...
Read more

Data Structures and Data Abstraction

  What is a Data Structure? A data structure is a way to organize, manage, and store data so that it can be used efficiently . It defines how data is arranged in memory and how operations like insertion , deletion , searching , and updating can be performed. In simple words: Data structures are like containers that hold data together in a certain format so that computers can easily access and modify them.   More formally   "A data structure is a mathematical and logical model of a particular organization of data. It describes the relationship among the data elements, and the operations that can be performed on them." ➔ Key points: Organization of data. Logical relationship between data elements. Set of operations that can be applied (like insert, delete, search, etc.). Key Points about Data Structures: They help in organizing large amounts of data easily. They improve the efficiency of algorithms. They decide how fast and efficient prog...
Read more