Recursion, Stack, Queue, and Tree Data Structures in Computer Science

Base Case

Stops recursion

Recursive Case

Smaller problem call

Call Stack

Each call is pushed onto the call stack until the base case is reached, then unwinds (LIFO order)

Factorial Definition

`if (n <= 1) return 1; else return n * factorial(n-1);`

Sum of Array Recursive Function

`if (n == 0) return 0; else return a[n-1] + sumArray(a, n-1);`

Time Complexity of Factorial

O(n)

Time Complexity of Fibonacci Recursion

O(2ⁿ)

Tail Recursion

Performs the recursive call as the last operation

Non-Tail Recursion

Does extra work after the call

Stack Data Structure

Linear structure; LIFO (Last In First Out)

Core Stack Operations

`push()`, `pop()`, `top()` - all O(1)

C++ STL Syntax for Stack

#include

stack S;

S.push(5);

S.top();

S.pop();

S.empty();

Common Uses of Stacks

Function call tracking, Undo/Redo, Backtracking, DFS, expression evaluation

Queue Data Structure

Linear structure; FIFO (First In First Out)

Core Queue Operations

`enqueue(push)`, `dequeue(pop)`, `front()`, `empty()` - O(1)

C++ STL Syntax for Queue

#include

queue Q;

Q.push(5);

Q.front();

Q.pop();

Q.empty();

Common Applications of Queues

CPU/job scheduling, BFS traversal, printer queues, order processing

Binary Tree

A hierarchical structure where each node has ≤ 2 children (left and right)

Full Binary Tree

0 or 2 children

Complete Binary Tree

Levels full except possibly last filled left→right

Perfect Binary Tree

All levels completely filled

Max Nodes in Height h Binary Tree

2^(h+1) - 1

Tree Height

Max edges root→leaf

Number of Edges in Tree

Nodes - 1

Tree Traversal Orders

Inorder (LNR), Preorder (NLR), Postorder (LRN), Level Order (BFS)

height(Node* r)

Returns the height of a binary tree.

Pseudocode for checking full binary tree

if (!root) return true; if (!root->left && !root->right) return true; if (root->left && root->right) return isFull(l) && isFull(r); return false;

Recursion data structure

The stack.

Space complexity of recursion

O(depth of recursion).

Big-O of Merge Sort

O(n log n).

Big-O of Binary Search

O(log n).

Big-O of Insertion Sort

Best O(n), Average/Worst O(n²).

Big-O of Selection Sort

O(n²).

Average time for tree traversal

O(n) - each node visited once.

Examples where a queue is faster than a stack

Breadth-First Search, task scheduling, buffer management.

Recursion vs iteration speed

Extra stack frames and function call overhead.

Choosing iterative vs recursive solutions

Use recursion for naturally divisible problems (trees, divide & conquer); iteration for simple loops.

C++ STL library header for stack and queue

#include and #include

Difference between front and top

Front = queue's first element; Top = stack's last inserted element.

Purpose of recursion in Merge Sort

Divide array into smaller parts, sort each recursively, then merge.

BFS traversal data structure

Queue.

DFS traversal data structure

Stack (or recursion stack).

Pros and cons of linked-list implementation of stack/queue

Pros: Dynamic size; Cons: Extra pointer memory and allocations.

Big-O notation O(1)

Constant time — execution time independent of input size.

Concept of O(log n)

Work reduces by half each step (e.g. binary search).

Typical use-cases of recursion on trees

Traversal, searching, computing height, sum, mirror, or leaf count.

Base case in recursive function

To prevent infinite recursion and stack overflow.

Steps to Implement Recursion

Step1 - Define a base case: Identify the simplest (or base) case for which the solution is known or trivial. This is the stopping condition for the recursion, as it prevents the function from infinitely calling itself.

Step2 - Define a recursive case: Define the problem in terms of smaller subproblems. Break the problem down into smaller versions of itself, and call the function recursively to solve each subproblem.

Step3 - Ensure the recursion terminates: Make sure that the recursive function eventually reaches the base case, and does not enter an infinite loop.

Step4 - Combine the solutions: Combine the solutions of the subproblems to solve the original problem.