Priority Queue and Deque; Trees — Introduction; Binary Tree — Data Structures and Algorithms

Priority Queue and Deque

Priority Queue

In a priority queue, elements are dequeued based on priority, not insertion order.

Types:

Type	Description
Max Priority Queue	Highest priority element dequeued first
Min Priority Queue	Lowest priority element dequeued first

Implementation:

Array with sorting
Binary Heap (most efficient — O(log n) insert and delete)

Applications:

Dijkstra's shortest path
Huffman encoding
OS scheduling (priority scheduler)
A* pathfinding

Deque — Double Ended Queue

DEQueue (Double Ended Queue): Elements can be added/removed from both ends.

Rear add ← [50][40][30][20][10] → Front remove
Front add → [50][40][30][20][10] ← Rear remove

Types of DEQueue:

Type	Description
Input Restricted Queue	Insertion only at rear; deletion from both ends
Output Restricted Queue	Deletion only from front; insertion at both ends

Applications:

Sliding window maximum problem
Palindrome checking
Task scheduling

Trees — Introduction

What is a Tree?

A Tree is a non-linear, hierarchical data structure consisting of nodes connected by edges.

Properties:

There is one special node called the root (no parent)
Every node (except root) has exactly one parent
Nodes can have zero or more children
There are no cycles in a tree (acyclic graph)

Tree Terminology

              [A]         ← Root (level 0)
            /     \
          [B]     [C]     ← Level 1 (children of A)
         /  \      |
       [D] [E]   [F]      ← Level 2 (leaves)

Term	Definition
Root	Topmost node; the single node with no parent
Parent	Node with children
Child	Node connected below a parent
Sibling	Nodes sharing the same parent (B and C)
Leaf / External node	Node with no children (D, E, F above)
Internal node	Node with at least one child (A, B, C)
Depth	Number of edges from root to the node
Height	Number of edges on the longest path from node to leaf
Subtree	Tree formed by a node and all its descendants
Degree	Number of children a node has
Level	Depth + 1 (root is at level 1 or 0 depending on convention)

Binary Tree

What is a Binary Tree?

A binary tree is a tree where every node has at most 2 children — a left child and a right child.

         [10]
        /    \
      [5]    [15]
      /  \   /  \
    [3] [7] [12] [20]

Types of Binary Trees

Type	Description
Full Binary Tree	Every node has 0 or 2 children
Complete Binary Tree	All levels filled except last; last level filled left to right
Perfect Binary Tree	All internal nodes have exactly 2 children; all leaves at same level
Skewed Binary Tree	All nodes have only left or only right child (worst case)
Balanced Binary Tree	Height difference between left and right subtrees ≤ 1 for all nodes

Binary Tree Node in C

typedef struct btnode {
    int data;
    struct btnode *left;   // pointer to left child
    struct btnode *right;  // pointer to right child
} btnode_t;

// Create a new node
btnode_t *new_node(int value) {
    btnode_t *node = (btnode_t*)malloc(sizeof(btnode_t));
    node->data = value;
    node->left = NULL;
    node->right = NULL;
    return node;
}

Properties of Binary Tree

For a binary tree with n nodes:

Minimum height: ⌈log₂(n+1)⌉ - 1 (when perfectly balanced)
Maximum height: n-1 (when skewed / linear tree)
Maximum nodes at level i: 2^i
Maximum nodes with height h: 2^(h+1) - 1
Number of leaf nodes = Number of internal nodes + 1 (for full binary tree)

Priority Queue and Deque; Trees — Introduction; Binary Tree