Data Structures

• 1: Stack
• 2: Queue / Deque
• 3: Heap
• 4: Binary Tree
• 4.1: 199. Binary Tree Right Side View
• 5: Linked List
• 6: Binary Search Tree
• 7: Bitset

1 - Stack

A stack is a Last-In-First-Out (LIFO) data structure that supports two main operations: push (insertion) and pop (deletion). In C++, you can use the built-in stack container from the Standard Template Library (STL).

Basic Stack Operations in C++

#include <stack>

// Declaration
stack<long long> mystack;  // Create an empty stack of long long integers

// Basic Operations
// 1. push(value) - Add element to top of stack - O(1)
mystack.push(6);  // mystack = [6]
mystack.push(3);  // mystack = [6, 3]
mystack.push(9);  // mystack = [6, 3, 9]

// 2. pop() - Remove element from top of stack - O(1)
mystack.pop();    // Removes 9, mystack = [6, 3]

// 3. top() - Get value of top element - O(1)
int topValue = mystack.top();  // Returns 3

// 4. size() - Get number of elements in stack - O(1)
int stackSize = mystack.size();  // Returns 2

// 5. empty() - Check if stack is empty - O(1)
bool isEmpty = mystack.empty();  // Returns false

Important Notes:

• Always check if stack is not empty before calling pop() or top()
• Stack has constant time O(1) complexity for all basic operations
• Stack is particularly useful for:
  • Function call management
  • Expression evaluation
  • Backtracking algorithms
  • Undo operations
  • Parentheses matching

Common Mistakes to Avoid:

1. Calling pop() or top() on empty stack
2. Not including <stack> header
3. Forgetting that pop() doesn’t return the removed value

Example Usage:

#include <stack>
#include <iostream>
using namespace std;

int main() {
    stack<int> st;
    
    // Push elements
    st.push(1);
    st.push(2);
    st.push(3);
    
    // Safe way to process stack
    while (!st.empty()) {
        cout << st.top() << " ";  // Print top element
        st.pop();                 // Remove top element
    }
    // Output: 3 2 1
    
    return 0;
}

Problems that demonstrate the effective use of stack data structure to solve algorithmic challenges.

2 - Queue / Deque

Problems that demonstrate the effective use of queue and double-ended queue data structures to solve algorithmic challenges.

3 - Heap

Problems that demonstrate the effective use of heap data structure (priority queue) to solve algorithmic challenges.

4 - Binary Tree

Problems that demonstrate the effective use of binary tree data structure to solve algorithmic challenges.

4.1 - 199. Binary Tree Right Side View

Problem Description

LeetCode Problem Link

Given the root of a binary tree, imagine yourself standing on the right side of it. Return the values of the nodes you can see ordered from top to bottom.

Constraints:

• The number of nodes in the tree is in the range [0, 100]
• -100 ≤ Node.val ≤ 100

Example:

Input: root = [1,2,3,null,5,null,4]
Output: [1,3,4]
Explanation: The nodes visible from the right side are 1, 3, and 4.

Intuition and Approach

Intuition

When viewing a binary tree from the right side, we want to see the rightmost node at each level. Using a queue for level-order traversal (BFS), we can capture the last node at each level to build our right-side view.

Approach

1. Use a queue to perform level-order traversal
2. For each level:
   • Get the current level size
   • Process all nodes at this level
   • Add the last node’s value to our result
3. Return the collected right-side values

/**
 * Definition for a binary tree node.
 * type TreeNode struct {
 *     Val int
 *     Left *TreeNode
 *     Right *TreeNode
 * }
 */
func rightSideView(root *TreeNode) []int {
    if root == nil {
        return []int{}
    }
    
    result := []int{}
    queue := []*TreeNode{root}
    
    for len(queue) > 0 {
        levelSize := len(queue)
        
        for i := 0; i < levelSize; i++ {
            node := queue[0]
            queue = queue[1:]
            
            // If it's the last node in current level, add to result
            if i == levelSize-1 {
                result = append(result, node.Val)
            }
            
            // Add children to queue
            if node.Left != nil {
                queue = append(queue, node.Left)
            }
            if node.Right != nil {
                queue = append(queue, node.Right)
            }
        }
    }
    
    return result
}

Time and Space Complexity

Time Complexity: O(n)

• Visit each node exactly once
• Queue operations are O(1)

Space Complexity: O(w)

• w is the maximum width of the tree
• In worst case (perfect binary tree), the last level has n/2 nodes
• Queue stores at most one level at a time

5 - Linked List

Problems that demonstrate the effective use of linked list data structure to solve algorithmic challenges.

6 - Binary Search Tree

Problems that demonstrate the effective use of binary search tree data structures (set/multiset, map/multimap) to solve algorithmic challenges.

7 - Bitset

Problems that demonstrate the effective use of bitset data structure to solve algorithmic challenges.