Data Structures & Algorithms

4.1Time & Space Complexity

Time and Space Complexity are used to measure the efficiency of an algorithm.

When solving a programming problem, it is not enough to know that a program produces the correct answer. We also need to understand:

• How much time will it take?
• How much memory will it use?
• How will its performance change when the input becomes very large?

For example, an algorithm that works well for 100 records may become extremely slow when processing 10 million records. Complexity analysis helps us identify such problems before they occur.

4.1.1What Is Algorithm Complexity?

• Suppose an algorithm processes an input containing n elements.
• We use n to represent the input size.
• For example:

numbers = [10, 20, 30, 40, 50]

Here:

n = 5

If the list contains one million elements:

n = 1,000,000

• Complexity analysis describes how the algorithm's resource requirements grow as n increases.
• There are two primary types:
• Time Complexity – how computation grows with input size.
• Space Complexity – how memory usage grows with input size.

4.1.2Time Complexity

• Time complexity describes how the number of operations performed by an algorithm grows as the input size increases.
• It does not normally mean the exact number of seconds required.
• Consider:

def print_numbers(numbers):
for number in numbers:
print(number)

If there are n elements, the loop executes n times.

Therefore:

Time Complexity = O(n)

If the input doubles, the number of iterations approximately doubles.

4.1.3Why Exact Execution Time Is Not Used

Suppose two computers execute the same program:

• Computer A → 2 seconds
• Computer B → 0.8 seconds
• The exact execution time depends on:
• CPU
• RAM
• Operating system
• Programming language
• Compiler/interpreter
• Background processes
• Hardware architecture

Therefore, algorithm analysis focuses on growth rate rather than machine-dependent execution time.

4.1.4Big-O Notation

• The most commonly used notation for describing algorithm complexity is Big-O notation.
• Big-O describes how an algorithm grows as the input size becomes large.
• Common complexities include:

A commonly remembered order is:

O(1)

↓

O(log n)

↓

O(n)

↓

↓

O(n!)

Generally, the complexity toward the top scales better for large inputs.

4.1.5O(1) — Constant Time

An algorithm has O(1) complexity when its execution does not depend on the size of the input.

Example:

numbers = [10, 20, 30, 40, 50]
value = numbers[2]

Accessing an element by index is generally:

O(1)

Whether the list contains 5 elements or 5 million elements, accessing a particular index is generally constant time.

Another example:

def get_first(numbers):
return numbers[0]

Complexity:

Time = O(1)

4.1.6O(n) — Linear Time

An algorithm is O(n) when its work grows proportionally with the input size.

Example:

def find_number(numbers, target):
for number in numbers:
if number == target:
return True
return False

In the worst case, every element must be checked.

Therefore:

Time = O(n)

For:

n = 100

approximately 100 elements may be examined.

For:

n = 1,000,000

approximately 1,000,000 elements may be examined.

4.1.7O(log n) — Logarithmic Time

• An algorithm has logarithmic complexity when the problem size is repeatedly reduced by a factor.
• The classic example is binary search.
• Suppose we have:

Binary search doesn't check every element.

Instead, it repeatedly divides the search space:

Therefore:

Time = O(log n)

This is why binary search is much faster than linear search for large sorted datasets.

4.1.8O(n²) — Quadratic Time

Quadratic complexity commonly occurs when one loop is nested inside another.

Example:

def print_pairs(numbers):
for i in numbers:
for j in numbers:
print(i, j)

The outer loop executes n times.

For every outer iteration, the inner loop also executes n times.

Therefore:

• n × n = n²
• So:
• Time = O(n²)
• If:

n = 1,000

• the algorithm can perform roughly:
• 1,000 × 1,000
• = 1,000,000
• iterations.

4.1.9O(n³) — Cubic Time

Three nested loops commonly result in O(n³).

def example(n):
for i in range(n):
for j in range(n):
for k in range(n):
print(i, j, k)

• The number of operations is approximately:
• n × n × n
• = n³

Therefore:

Time = O(n³)

Such algorithms become expensive very quickly as n grows.

4.1.10O(n log n)

• O(n log n) is an important complexity in efficient algorithms.
• It is commonly associated with:
• Merge Sort
• Heap Sort
• Average-case Quick Sort

For example, Merge Sort repeatedly divides the input into smaller pieces and then processes the elements at each level.

The result is:

Time = O(n log n)

This is generally much better than O(n²) for large datasets.

4.1.11O(2ⁿ) — Exponential Time

An exponential algorithm grows extremely quickly.

A classic example is naive recursive Fibonacci:

def fibonacci(n):
if n <= 1:
return n
return fibonacci(n - 1) + fibonacci(n - 2)

The function creates multiple recursive branches.

Its time complexity is exponential, commonly represented as:

• O(2ⁿ)
• This approach becomes impractical for relatively small values of n.
• Dynamic Programming can dramatically improve this problem.

4.1.12O(n!) — Factorial Time

Factorial complexity commonly appears when an algorithm tries every possible permutation.

For example:

3! = 6

• 5! = 120
• 10! = 3,628,800
• 15! = 1,307,674,368,000

Therefore, algorithms with O(n!) complexity become impractical very quickly.

4.1.13Best Case, Average Case and Worst Case

An algorithm may behave differently depending on the input.

Consider linear search:

def search(numbers, target):
for number in numbers:
if number == target:
return True
return False

Best Case

The target is the first element.

Time = O(1)

Average Case

The target is somewhere in the middle.

Time = O(n)

Worst Case

• The target is the last element or doesn't exist.
• Time = O(n)
• When discussing algorithm complexity, worst-case complexity is often emphasized.

4.1.14Space Complexity

Space complexity describes how the memory requirements of an algorithm grow with input size.

Consider:

def calculate_sum(numbers):
    total = 0
    for number in numbers:
        total += number

return total

Only a few variables are created regardless of the number of elements.

Therefore, the auxiliary space is:

O(1)

4.1.15O(n) Space Complexity

Consider:

def duplicate(numbers):
    result = []
    for number in numbers:
        result.append(number)

return result

The result list grows as the input grows.

If the input contains n elements, the new list also contains approximately n elements.

Therefore:

Space = O(n)

4.1.16Time Complexity vs Space Complexity

Consider this algorithm:

def find_duplicates(numbers):
seen = set()
for number in numbers:
if number in seen:
return True

seen.add(number)

return False

The algorithm may process every element once:

Time = O(n)

The seen set may contain n elements:

Space = O(n)

Therefore:

Time Complexity = O(n)

Space Complexity = O(n)

4.1.17Time-Space Tradeoff

Sometimes we can make an algorithm faster by using additional memory.

For example, finding duplicates using nested loops:

for i in range(n):
for j in range(i + 1, n):
if numbers[i] == numbers[j]:
return True

has approximately:

Time = O(n²)

Space = O(1)

Using a set:

seen = set()
for number in numbers:
if number in seen:
return True

seen.add(number)

gives approximately:

Time = O(n)

Space = O(n)

We use additional memory to improve execution time.

This is called a time-space tradeoff.

4.1.18Big-O, Big-Ω and Big-Θ

• Three important asymptotic notations are:
• Big-O — O()
• Represents an asymptotic upper bound.

Example:

O(n)

Big-Omega — Ω()

Represents an asymptotic lower bound.

Example:

Ω(1)

Big-Theta — Θ()

Represents a tight asymptotic bound.

Example:

Θ(n)

For practical DSA and coding interviews, Big-O is the notation you will encounter most frequently.

4.1.19Dropping Constants

• Suppose an algorithm performs:
• 5n + 10
• operations.
• We write:
• O(5n + 10)
• For asymptotic analysis, constants are ignored:

O(n)

• Similarly:
• O(3n² + 5n + 100)
• becomes:
• O(n²)

because n² is the dominant growth term.

4.1.20Sequential Operations

Consider:

for i in range(n):
print(i)
for j in range(n):
print(j)

• The total work is:
• n + n
• = 2n

Therefore:

O(2n)

is simplified to:

O(n)

Sequential loops generally add their complexities rather than multiply them.

4.1.21Nested Operations

Consider:

for i in range(n):
for j in range(n):
print(i, j)

Here the loops are nested.

Therefore:

• n × n
• = n²
• So:
• O(n²)
• A useful rule is:

Sequential loops usually add; nested loops usually multiply.

4.1.22Different Input Sizes

Consider:

for i in range(n):
for j in range(m):
print(i, j)

The complexity is:

O(n × m)

or:

O(nm)

We should not automatically write O(n²) unless n and m represent the same input size.

4.1.23Recursive Space Complexity

Recursion also consumes memory because each function call is stored on the call stack.

Example:

def factorial(n):
if n == 0:
return 1
return n * factorial(n - 1)

• For:
• factorial(4)
• the call stack looks conceptually like:

There can be n active calls.

Therefore:

Time = O(n)

Space = O(n)

4.1.24Amortized Complexity

• Some operations are occasionally expensive but inexpensive on average over a sequence of operations.
• For example, Python's:
• numbers.append(value)
• has an amortized time complexity of O(1).

Occasionally, the underlying dynamic array may need to resize, which requires copying elements.

That individual resize can take O(n), but across many append operations, the average cost remains:

O(1) amortized

This concept is called amortized analysis.

4.1.25Common Python Data Structure Complexity

Python List

Python Dictionary

Python Set

These are typical/average-case complexities; implementation details and pathological cases can differ.

4.1.26Common Algorithm Complexities

4.1.27Graph Complexity

• For graph algorithms, we commonly use:
• V = Number of vertices
• E = Number of edges

Breadth-First Search (BFS) and Depth-First Search (DFS) typically have:

Time = O(V + E)

This is because the algorithm may visit each vertex and edge.

Their auxiliary space is typically:

Space = O(V)

4.1.28Practical Example: Two Sum

Suppose we need to find two numbers whose sum equals a target.

Brute Force

def two_sum(numbers, target):
for i in range(len(numbers)):
for j in range(i + 1, len(numbers)):
if numbers[i] + numbers[j] == target:
return i, j
return None

There are nested loops.

Therefore:

Time = O(n²)

Space = O(1)

Optimized Approach

def two_sum(numbers, target):
seen = {}
for i, number in enumerate(numbers):
required = target - number
if required in seen:
return seen[required], i

seen[number] = i

return None

Now:

Time = O(n)

Space = O(n)

The optimized solution is faster for large inputs because it uses additional memory.

4.1.29How to Analyze an Algorithm

When analyzing an algorithm, follow this process:

• Step 1: Identify the input size
• Determine what n represents.
• Step 2: Identify loops
• Determine how many times each loop executes.
• Step 3: Check nested loops
• Nested loops often multiply their complexities.
• Step 4: Check recursion
• Determine:
• Number of recursive calls
• Recursion depth
• Number of branches
• Step 5: Identify additional data structures
• Look for:
• Lists
• Sets
• Dictionaries
• Arrays
• Queues
• Stacks
• Temporary variables
• Step 6: Find the dominant term
• For example:
• O(n² + n + 10)
• becomes:
• O(n²)
• Step 7: State both complexities
• Always try to report:
• Time Complexity = ?
• Space Complexity = ?

4.1.30Complexity Comparison

For a very large input, the difference between complexity classes becomes significant.

For example, when n becomes very large:

O(log n) << O(n) << O(n²) << O(2ⁿ)

This is why algorithm selection becomes increasingly important as datasets grow.

4.1.31Important Rules to Remember

Rule 1 — One loop

for i in range(n):

...

O(n)

Rule 2 — Two nested loops

for i in range(n):
for j in range(n):

...

• O(n²)
• Rule 3 — Three nested loops
• O(n³)
• Rule 4 — Halving the search space
• O(log n)
• Rule 5 — Efficient comparison sorting
• O(n log n)
• Rule 6 — Hash-table lookup
• Typically:
• O(1) average
• Rule 7 — Additional collection containing n elements
• Usually:
• O(n) space
• Rule 8 — Recursive depth of n
• Often:
• O(n) stack space

4.1.32Interview Questions

Question 1

What is time complexity?

Answer: Time complexity describes how the computational work of an algorithm grows as the input size increases.

Question 2

What is space complexity?

Answer: Space complexity describes how the memory requirements of an algorithm grow as the input size increases.

Question 3

What is Big-O notation?

Answer: Big-O notation describes the asymptotic upper-bound growth rate of an algorithm.

Question 4

What is the complexity of accessing an array element by index?

Answer:

O(1)

Question 5

What is the complexity of linear search?

Answer:

Worst Case = O(n)

Question 6

What is the complexity of binary search?

Answer:

O(log n)

assuming the data is sorted and the search is implemented appropriately.

Question 7

What is the complexity of merge sort?

Answer:

O(n log n)

Question 8

What is a time-space tradeoff?

Answer: A time-space tradeoff occurs when additional memory is used to reduce execution time, or when less memory is used at the cost of additional computation.

4.1.33Practice Problems

Problem 1

Find the time complexity:

for i in range(n):
print(i)

Answer:

O(n)

Problem 2

for i in range(n):
for j in range(n):
print(i, j)

Answer:

O(n²)

Problem 3

numbers = []
for i in range(n):
    numbers.append(i)

Answer:

Time = O(n)

• Space = O(n)
• Problem 4
• numbers.sort()

for number in numbers:
print(number)

Answer:

Sorting = O(n log n)

Traversal = O(n)

Overall = O(n log n)

The dominant term determines the final complexity.

4.1.34Summary

Time and Space Complexity are essential for evaluating algorithm efficiency.

The most important complexities to remember are:

O(1) → Constant

O(log n) → Logarithmic

O(n) → Linear

O(n log n) → Linearithmic

O(n²) → Quadratic

O(n³) → Cubic

O(2ⁿ) → Exponential

O(n!) → Factorial

The key objective of complexity analysis is to understand how an algorithm behaves as the input becomes larger, rather than focusing only on whether the algorithm works for a small example.

For DSA interviews and real-world software development, always ask:

• 1. What is the input size?
• 2. How many times does the algorithm process the input?
• 3. Are there nested loops?
• 4. Is recursion involved?
• 5. What additional memory is required?
• 6. Can the time complexity be reduced?
• 7. Can memory be reduced?

Once these questions become natural, you will have a strong foundation for the remaining topics in Module 4 – Data Structures & Algorithms.

An array is a linear data structure used to store multiple elements in a sequence.

Arrays are one of the most fundamental data structures because they provide efficient access to elements using an index.

For example:

Index: 0 1 2 3 4

↓ ↓ ↓ ↓ ↓

Array: 10 20 30 40 50

In Python, the built-in list is commonly used when we need array-like behavior.

numbers = [10, 20, 30, 40, 50]

4.2.1Characteristics of Arrays

An array generally has the following characteristics:

Stores multiple values.

• Elements are accessed using indexes.
• Elements are stored in a logical sequence.
• Supports traversal.
• Supports searching and updating.
• Provides fast indexed access.

Can be used to implement other data structures.

In Python, lists are dynamic arrays, meaning they can grow and shrink as elements are added or removed.

4.2.2Creating an Array in Python

The simplest approach is using a list:

numbers = [10, 20, 30, 40, 50]

We can also create an empty list:

numbers = []

Then add elements:

• numbers.append(10)
• numbers.append(20)
• numbers.append(30)
• The result is:

4.2.3Accessing Array Elements

Array elements are accessed using their index.

numbers = [10, 20, 30, 40, 50]
print(numbers[0])
print(numbers[2])
print(numbers[4])

Output:

• 10
• 30
• 50
• Python uses zero-based indexing.

Therefore:

• Index 0 → First element
• Index 1 → Second element
• Index 2 → Third element

...

The last element can also be accessed using:

numbers[-1]

4.2.4Updating an Array Element

An existing element can be modified using its index.

numbers = [10, 20, 30, 40, 50]

numbers[2] = 35

print(numbers)

Output:

The update operation is generally:

Time Complexity = O(1)

4.2.5Traversing an Array

Traversal means visiting every element.

Using a for loop

numbers = [10, 20, 30, 40, 50]
for number in numbers:
print(number)

Output:

• 10
• 20
• 30
• 40
• 50
• Time complexity:

O(n)

because every element is visited.

4.2.6Traversal Using Indexes

We can also traverse using indexes:

numbers = [10, 20, 30, 40, 50]
for i in range(len(numbers)):
print(numbers[i])

This approach is useful when we need both the index and value.

A more Pythonic approach is:

for index, value in enumerate(numbers):
print(index, value)

4.2.7Inserting Elements

Python lists provide several ways to insert elements.

Append

Adds an element to the end.

numbers = [10, 20, 30]

numbers.append(40)

print(numbers)

Result:

Appending is generally:

O(1) amortized

Insert at a Specific Position

numbers = [10, 20, 30, 40]

numbers.insert(2, 25)

print(numbers)

Result:

Elements after the insertion position need to be shifted.

Therefore:

Time Complexity = O(n)

4.2.8Deleting Elements

Delete by Index

numbers = [10, 20, 30, 40]

del numbers[1]

print(numbers)

Result:

Deleting from the middle requires shifting elements.

Therefore:

Time Complexity = O(n)

Remove by Value

numbers = [10, 20, 30, 40]

numbers.remove(30)

print(numbers)

Result:

Searching for the value requires traversal:

O(n)

Therefore, remove() is generally:

O(n)

Pop from the End

numbers = [10, 20, 30]
value = numbers.pop()
print(value)

Output:

30

Removing from the end is generally:

O(1)

Pop from the Beginning

numbers = [10, 20, 30]

numbers.pop(0)

The remaining elements must shift.

Therefore:

O(n)

4.2.9Array Operations and Complexity

Understanding these complexities is important when designing efficient algorithms.

4.2.10Searching an Array

Searching means finding whether a particular element exists.

Consider:

numbers = [10, 20, 30, 40, 50]
target = 30
if target in numbers:
print("Found")

For an unsorted list, searching generally requires:

O(n)

4.2.11Linear Search

A linear search checks elements one by one.

def linear_search(numbers, target):
for i in range(len(numbers)):
if numbers[i] == target:
return i
return -1

Example:

numbers = [10, 20, 30, 40, 50]
result = linear_search(numbers, 40)
print(result)

Output:

3

Complexity:

Best Case = O(1)

Worst Case = O(n)

Space = O(1)

4.2.12Finding the Maximum Element

We can find the maximum value using a single traversal.

def find_max(numbers):
maximum = numbers[0]
for number in numbers:
if number > maximum:
maximum = number
return maximum

Example:

numbers = [12, 5, 30, 8, 25]
print(find_max(numbers))

Output:

30

Complexity:

Time = O(n)

Space = O(1)

4.2.13Finding the Minimum Element

def find_min(numbers):
minimum = numbers[0]
for number in numbers:
if number < minimum:
minimum = number
return minimum

Complexity:

Time = O(n)

Space = O(1)

4.2.14Calculating the Sum

def array_sum(numbers):
    total = 0
    for number in numbers:
        total += number

return total

Example:

numbers = [10, 20, 30, 40]
print(array_sum(numbers))

Output:

100

Complexity:

Time = O(n)

Space = O(1)

4.2.15Reversing an Array

An array can be reversed using two pointers.

def reverse_array(numbers):
    left = 0
    right = len(numbers) - 1
    while left < right:
        numbers[left], numbers[right] = numbers[right], numbers[left]

left += 1

right -= 1

return numbers

Example:

numbers = [10, 20, 30, 40, 50]
print(reverse_array(numbers))

Output:

Complexity:

Time = O(n)

Space = O(1)

This is an important interview pattern.

4.2.16Finding the Second Largest Element

A common interview problem is finding the second-largest value without sorting.

def second_largest(numbers):
largest = float("-inf")
second = float("-inf")
for number in numbers:
if number > largest:
second = largest
largest = number
elif largest > number > second:
second = number
return second

Example:

numbers = [10, 40, 20, 50, 30]
print(second_largest(numbers))

Output:

40

Complexity:

Time = O(n)

• Space = O(1)
• A sorting-based solution would typically require:
• O(n log n)

so the single-pass solution is more efficient.

4.2.17Removing Duplicates

Suppose:

numbers = [1, 2, 2, 3, 4, 4, 5]

We want:

A simple solution is:

unique = list(set(numbers))

This is convenient, but a set does not preserve the original ordering in the same conceptual way as a sequence.

If order matters, use:

def remove_duplicates(numbers):
    seen = set()
    result = []
    for number in numbers:
        if number not in seen:
            seen.add(number)

result.append(number)

return result

Typical complexity:

Time = O(n)

Space = O(n)

4.2.18Prefix Sum

A prefix sum stores cumulative sums.

Given:

the prefix sum becomes:

Implementation:

def prefix_sum(numbers):
result = [0] * len(numbers)

result[0] = numbers[0]

for i in range(1, len(numbers)):
    result[i] = result[i - 1] + numbers[i]

return result

Time complexity:

O(n)

Space complexity:

O(n)

Prefix sums are extremely useful for range-sum problems.

4.2.19Array Range Sum

Suppose we have:

numbers = [2, 4, 6, 8, 10]

and need the sum between indexes 1 and 3.

That means:

4 + 6 + 8 = 18

Using prefix sums:

prefix = [2, 6, 12, 20, 30]

The range sum can be calculated as:

• prefix[3] - prefix[0]
• = 20 - 2
• = 18

This changes repeated range-sum queries from potentially O(n) each to approximately O(1) after O(n) preprocessing.

4.2.20Two-Dimensional Arrays

A two-dimensional array can represent a matrix.

matrix = [
    [1, 2, 3],
    [4, 5, 6],

]

It can be visualized as:

1 2 3

4 5 6

7 8 9

Access:

print(matrix[1][2])

Output:

6

The first index represents the row and the second represents the column.

4.2.21Traversing a Matrix

matrix = [
    [1, 2, 3],
    [4, 5, 6],

]

for row in matrix:
for value in row:
print(value)

For an m × n matrix:

Time = O(m × n)

If the matrix is n × n:

Time = O(n²)

4.2.22Transposing a Matrix

The transpose converts rows into columns.

Original:

1 2 3

4 5 6

Transpose:

1 4

2 5

3 6

Using Python:

matrix = [
    [1, 2, 3],

]

transpose = [list(row) for row in zip(*matrix)]
print(transpose)

Output:

4.2.23Common Array Interview Patterns

Arrays appear frequently in coding interviews.

Important patterns include:

1. Traversal

Visit each element once.

Typical complexity:

O(n)

2. Two Pointers

• Useful for:
• Reversing arrays
• Pair-sum problems
• Removing duplicates
• Sorted arrays

3. Sliding Window

• Useful for:
• Maximum subarray problems
• Longest substring problems
• Fixed-size windows

4. Prefix Sum

• Useful for:
• Range-sum queries
• Subarray calculations

5. Hashing

• Useful for:
• Duplicate detection
• Frequency counting
• Two Sum
• Lookup problems

6. Binary Search

Useful when the data or search space has the required ordering/monotonic property.

4.2.24Frequency Counting

Suppose we want to count how many times each number appears.

def frequency(numbers):
    counts = {}
    for number in numbers:
        counts[number] = counts.get(number, 0) + 1

return counts

Example:

numbers = [1, 2, 2, 3, 3, 3]
print(frequency(numbers))

Result:

{1: 1, 2: 2, 3: 3}

Typical complexity:

Time = O(n)

Space = O(n)

4.2.25Maximum Subarray Problem

One of the most famous array problems is finding the contiguous subarray with the maximum sum.

For:

the maximum-sum subarray is:

with sum:

6

This can be solved efficiently using Kadane's Algorithm.

def max_subarray(numbers):
current = numbers[0]
maximum = numbers[0]
for number in numbers[1:]:
current = max(number, current + number)
maximum = max(maximum, current)
return maximum

Complexity:

Time = O(n)

Space = O(1)

This is an important example of optimizing an apparently difficult problem.

4.2.26Array Rotation

Suppose:

is rotated to the right by two positions:

A simple Python approach is:

def rotate(numbers, k):
    k %= len(numbers)

return numbers[-k:] + numbers[:-k]

This creates additional lists, so the auxiliary space is proportional to n.

An in-place reversal technique can perform the rotation with:

Time = O(n)

Space = O(1)

4.2.27Advantages of Arrays

Arrays provide several benefits:

Fast indexed access

O(1)

• Simple structure
• Arrays are easy to understand and implement.
• Efficient traversal
• Sequential access is straightforward.
• Good cache locality
• Contiguous storage in traditional arrays can make sequential processing efficient.
• Foundation for other data structures
• Arrays are commonly used to implement:
• Stacks
• Queues
• Heaps
• Hash tables
• Matrices

4.2.28Disadvantages of Arrays

Arrays also have limitations:

Inserting into the beginning or middle can be expensive.

O(n)

Deleting from the beginning or middle can be expensive.

O(n)

• Traditional fixed-size arrays have limited capacity.
• Maintaining ordered elements can make insertion expensive.
• Searching an unsorted array is generally:

O(n)

4.2.29Arrays vs Linked Lists

* Assuming a pointer/reference to the head is already available.

4.2.30Arrays in AI and Machine Learning

Arrays are especially important in AI and Machine Learning.

For example:

features = [5.2, 3.1, 7.8, 2.4]

A dataset can be represented as a matrix:

Feature 1 Feature 2 Feature 3

Sample 1 10 20 30

Sample 2 15 25 35

Sample 3 20 30 40

Machine-learning libraries such as NumPy represent these structures using multidimensional arrays.

For example:

import numpy as np
X = np.array([
    [10, 20, 30],
    [15, 25, 35],

])

• Arrays therefore form the foundation for:
• Feature matrices
• Images
• Tensors
• Model parameters
• Embeddings
• Numerical computation
• Matrix operations

4.2.31Important Array Problems

You should practice these problems before moving to the next data structure:

Beginner

• Find the maximum element.
• Find the minimum element.
• Calculate the sum.
• Calculate the average.
• Reverse an array.
• Count even and odd numbers.
• Search for an element.
• Find the second-largest element.
• Remove duplicates.
• Count frequencies.

Intermediate

• Rotate an array.
• Move zeros to the end.
• Find missing number.
• Find duplicate number.
• Two Sum.
• Merge two sorted arrays.
• Find intersection of two arrays.
• Find the maximum subarray.
• Find leaders in an array.
• Find a majority element.

Advanced

• Product of array except self.
• Three Sum.
• Container With Most Water.
• Trapping Rain Water.
• Maximum Product Subarray.
• Subarray Sum Equals K.
• Longest Consecutive Sequence.
• Merge Intervals.
• Search in a Rotated Sorted Array.
• Median of Two Sorted Arrays.

4.2.32Key Takeaways

The most important concepts to remember are:

Array indexing → O(1)

Array traversal → O(n)

Linear search → O(n)

Binary search → O(log n)

Append → O(1) amortized

Insert at beginning → O(n)

Delete at beginning → O(n)

Sorting → O(n log n)

Reverse in-place → O(n) time, O(1) space

Prefix sum → O(n) preprocessing

Hash-based lookup → O(1) average

The most important idea is that arrays provide extremely fast indexed access, but insertion and deletion in the middle or beginning can be expensive because elements may need to be shifted.

Arrays are therefore the foundation for many DSA techniques, including two pointers, sliding window, prefix sums, binary search, hashing, and dynamic programming.

A string is a sequence of characters used to represent text.

Strings are one of the most frequently used data types in programming and are especially important in Data Structures & Algorithms, because many interview problems involve searching, comparing, transforming, and analyzing text.

Examples:

name = "Sreehari"
message = "Welcome to Python"
email = "sreehari@example.com"

A string can be viewed as a sequence of characters:

String: P Y T H O N

Index: 0 1 2 3 4 5

4.3.1Characteristics of Strings

• Important characteristics of strings include:
• Strings are sequences of characters.
• Python strings use zero-based indexing.
• Strings are immutable in Python.
• Individual characters can be accessed using indexes.
• Strings support slicing.

Strings can be searched, compared, split, joined, and transformed.

Python provides many built-in string methods.

Example:

text = "Python"
print(text[0])
print(text[2])

Output:

P

t

4.3.2Creating Strings

Strings can be created using single quotes:

name = 'Sreehari'

Double quotes:

name = "Sreehari"

Triple quotes:

message = """This is

a multiline

• string."""
• Single and double quotes are commonly used for normal strings.
• Triple-quoted strings are useful for multiline text and documentation.

4.3.3String Indexing

Python strings use zero-based indexing.

text = "Python"

The indexes are:

P y t h o n

↓ ↓ ↓ ↓ ↓ ↓

0 1 2 3 4 5

Example:

print(text[0])
print(text[3])
print(text[5])

Output:

• P
• h
• n

4.3.4Negative Indexing

Python also supports negative indexes.

P y t h o n

-6 -5 -4 -3 -2 -1

Example:

text = "Python"
print(text[-1])
print(text[-2])

Output:

n

o

This is particularly useful when accessing characters from the end.

4.3.5String Length

Use len() to find the number of characters.

text = "Python"
print(len(text))

Output:

6

Time complexity:

O(1)

for Python strings because the length is stored as part of the string object's metadata.

4.3.6String Slicing

Slicing extracts part of a string.

Syntax:

string[start:end]

Example:

text = "Python"
print(text[0:3])

Output:

• Pyt
• The end index is excluded.
• Other Examples

text = "Python"
print(text[:3])
print(text[2:])
print(text[1:5])
print(text[:])

Output:

• Pyt
• thon
• ytho
• Python

4.3.7String Step

Slicing also supports a step.

text = "Python"
print(text[::2])

Output:

Pto

This takes every second character.

4.3.8Reversing a String

A simple Python technique is:

text = "Python"
reversed_text = text[::-1]
print(reversed_text)

Output:

nohtyP

Time complexity:

O(n)

Space complexity:

O(n)

because a new string is created.

4.3.9Strings Are Immutable

One of the most important properties of Python strings is immutability.

Consider:

text = "Python"

text[0] = "J"

This produces an error because individual characters cannot be modified directly.

Instead, create a new string:

text = "Python"
text = "J" + text[1:]
print(text)

Output:

Jython

4.3.10Why String Immutability Matters

Consider repeatedly modifying a string:

text = ""
for i in range(1000):
    text += str(i)

Because strings are immutable, repeated concatenation can create many intermediate string objects.

For large-scale string construction, use a list and join():

parts = []
for i in range(1000):
    parts.append(str(i))

text = "".join(parts)

This is generally more efficient.

4.3.11String Concatenation

Strings can be joined using +.

first_name = "Sreehari"
last_name = "Mekala"
full_name = first_name + " " + last_name
print(full_name)

Output:

Sreehari Mekala

For many pieces, prefer:

words = ["Python", "is", "powerful"]
sentence = " ".join(words)
print(sentence)

Output:

Python is powerful

4.3.12Membership Testing

Use in to determine whether a substring or character exists.

text = "Python Programming"
print("Python" in text)
print("Java" in text)

Output:

True

False

For a general substring search, the complexity can be proportional to the lengths of the strings involved.

For simple DSA analysis, it is important not to automatically assume every string operation is O(1).

4.3.13Searching for a Character

text = "Python"
print(text.find("t"))

Output:

2

If the substring is not found:

print(text.find("z"))

Output:

-1

4.3.14index() vs find()

Both can locate substrings.

text = "Python"
print(text.find("t"))

• returns:
• 2
• But:
• text.index("z")

raises a ValueError if the substring is not found.

Therefore:

find() → returns -1

index() → raises an exception

4.3.15Counting Characters

Use count():

text = "banana"
print(text.count("a"))

Output:

3

This is useful in frequency-related problems.

4.3.16Converting Case

Python provides several methods.

text = "Python Programming"
print(text.upper())
print(text.lower())
print(text.title())

Output:

• PYTHON PROGRAMMING
• python programming
• Python Programming
• Other useful methods include:
• text.capitalize()
• text.swapcase()

4.3.17Checking String Properties

Python provides useful methods:

text = "Python123"
print(text.isalpha())
print(text.isdigit())
print(text.isalnum())

Output:

• False
• False
• True
• Other methods include:
• isupper()
• islower()
• isspace()
• startswith()
• endswith()

4.3.18Removing Whitespace

Use strip():

text = "   Python   "
print(text.strip())

Output:

• Python
• Related methods:
• text.lstrip()
• text.rstrip()
• strip() → both sides
• lstrip() → left side
• rstrip() → right side

4.3.19Splitting Strings

The split() method converts a string into a list.

text = "Python is easy"
words = text.split()
print(words)

Output:

You can specify a delimiter:

data = "apple,banana,orange"
fruits = data.split(",")
print(fruits)

Output:

4.3.20Joining Strings

The opposite of split() is often join().

words = ["Python", "is", "easy"]
sentence = " ".join(words)
print(sentence)

Output:

Python is easy

Another example:

letters = ["P", "y", "t", "h", "o", "n"]
word = "".join(letters)
print(word)

Output:

Python

4.3.21String Formatting

Python supports several approaches.

f-strings

name = "Sreehari"
age = 37
message = f"My name is {name} and I am {age} years old."
print(message)

f-strings are generally the preferred modern Python approach.

4.3.22Comparing Strings

Strings can be compared using comparison operators.

a = "apple"
b = "banana"
print(a == b)
print(a != b)

Output:

• False
• True
• Lexicographical comparison is also possible:

print("apple" < "banana")

Output:

True

The comparison follows character ordering rules.

4.3.23String Traversal

A string can be traversed character by character.

text = "Python"
for character in text:
print(character)

Output:

• P
• y
• t
• h
• o
• n
• Time complexity:

O(n)

4.3.24Character Frequency

One of the most common string interview problems is counting character frequencies.

def character_frequency(text):
    frequency = {}
    for character in text:
        frequency[character] = frequency.get(character, 0) + 1

return frequency

Example:

text = "banana"
print(character_frequency(text))

Result:

{'b': 1, 'a': 3, 'n': 2}

Typical complexity:

Time = O(n)

Space = O(k)

where k is the number of distinct characters.

4.3.25Check for Palindrome

• A palindrome reads the same forward and backward.
• Examples:
• madam
• level
• racecar
• A simple solution:

def is_palindrome(text):
return text == text[::-1]

Example:

print(is_palindrome("madam"))

Output:

True

Complexity:

Time = O(n)

Space = O(n)

because slicing creates a reversed string.

4.3.26Palindrome Using Two Pointers

We can avoid creating a reversed copy.

def is_palindrome(text):
left = 0
right = len(text) - 1
while left < right:
if text[left] != text[right]:
return False

left += 1

right -= 1

return True

Complexity:

Time = O(n)

Space = O(1)

This is an important example of the two-pointer technique.

4.3.27Reverse Words in a String

• Given:
• "Python is powerful"
• we may want:
• "powerful is Python"

Solution:

def reverse_words(text):
words = text.split()

words.reverse()

return " ".join(words)

• Result:
• powerful is Python
• Typical complexity:

Time = O(n)

Space = O(n)

4.3.28Anagram

• Two strings are anagrams if they contain the same characters with the same frequencies.
• For example:
• listen
• silent
• are anagrams.
• A simple solution:

def are_anagrams(a, b):
return sorted(a) == sorted(b)

• Complexity:
• Time = O(n log n)
• because sorting is required.
• A frequency-based solution can achieve approximately:
• Time = O(n)

def are_anagrams(a, b):
    if len(a) != len(b):
        return False
        counts = {}
        for character in a:
            counts[character] = counts.get(character, 0) + 1

for character in b:
if character not in counts:
return False

counts[character] -= 1

return all(value == 0 for value in counts.values())

4.3.29Remove Duplicate Characters

Suppose:

"programming"

We want unique characters while preserving their first occurrence.

def remove_duplicates(text):
    seen = set()
    result = []
    for character in text:
        if character not in seen:
            seen.add(character)

result.append(character)

return "".join(result)

Example:

print(remove_duplicates("programming"))

• Result:
• progamin
• Typical complexity:

Time = O(n)

Space = O(k)

where k is the number of distinct characters.

4.3.30First Non-Repeating Character

• Given:
• "swiss"
• The first non-repeating character is:

"w"

Solution:

def first_unique(text):
    frequency = {}
    for character in text:
        frequency[character] = frequency.get(character, 0) + 1

for character in text:
if frequency[character] == 1:
return character
return None

Complexity:

Time = O(n)

Space = O(k)

4.3.31Check if Two Strings Are Rotations

• Consider:
• "abcd"
• A rotation could be:
• "cdab"
• A useful observation is:
• "abcd" + "abcd"
• contains:
• "cdab"

Therefore:

def are_rotations(a, b):
return len(a) == len(b) and b in (a + a)

Example:

print(are_rotations("abcd", "cdab"))

Output:

True

4.3.32Longest Common Prefix

Given:

the longest common prefix is:

"fl"

A simple approach:

def longest_common_prefix(words):
if not words:
return ""
prefix = words[0]
for word in words[1:]:
while not word.startswith(prefix):
prefix = prefix[:-1]
if not prefix:
return ""
return prefix

This problem introduces important ideas related to:

• String comparison
• Prefix searching
• Iterative reduction

A Trie, covered later in this module, provides another powerful approach to prefix-related problems.

4.3.33Substrings

• A substring is a contiguous sequence of characters.
• For:
• "abc"
• some substrings are:
• a
• b
• c
• ab
• bc
• abc

For a string of length n, the number of possible non-empty substrings is:

n(n + 1) / 2

Therefore, there can be:

O(n²)

substrings.

4.3.34Subsequences

• A subsequence does not have to contain contiguous characters.
• For:
• "abc"
• examples include:
• a
• b
• c
• ab
• ac
• bc
• abc
• Unlike substrings, characters can be skipped.

For a string of length n, there are:

2ⁿ

possible subsequences, including the empty subsequence.

Therefore, problems involving all subsequences can often have exponential complexity.

4.3.35Substring vs Subsequence

This distinction is extremely important in DSA problems.

4.3.36Longest Substring Without Repeating Characters

This is a classic interview problem.

Given:

"abcabcbb"

the longest substring without repeated characters is:

• "abc"
• with length:
• 3
• A brute-force approach can be expensive.

The efficient solution uses the sliding window technique:

def longest_unique_substring(text):
    seen = set()
    left = 0
    maximum = 0
    for right in range(len(text)):
        while text[right] in seen:
            seen.remove(text[left])

left += 1

seen.add(text[right])

maximum = max(maximum, right - left + 1)
return maximum

Complexity:

Time = O(n)

Space = O(k)

where k is the number of distinct characters.

4.3.37String Matching

• String matching means finding one string inside another.
• For example:
• Text:
• "Python programming language"
• Pattern:
• "programming"
• We want to determine where the pattern occurs.
• Python provides:
• text.find(pattern)

For advanced DSA, important string-matching algorithms include:

• Naive String Matching
• KMP Algorithm
• Rabin-Karp Algorithm
• Boyer-Moore Algorithm

These algorithms become important when processing large amounts of text efficiently.

4.3.38Naive String Matching

Suppose:

Text    = "ABABDABACD"
Pattern = "ABAC"

The naive approach compares the pattern at each possible position.

In the worst case, its complexity can be approximately:

O(n × m)

• where:
• n = text length
• m = pattern length

4.3.39KMP Algorithm

The Knuth-Morris-Pratt (KMP) algorithm improves string matching by avoiding unnecessary comparisons.

It builds an auxiliary structure called the:

LPS array

• LPS stands for:
• Longest Proper Prefix which is also a Suffix.
• KMP can perform pattern matching in:

O(n + m)

time.

It is an important advanced string algorithm.

4.3.40String Complexity Summary

Because Python strings are immutable, many operations create new strings.

4.3.41Strings in AI and Machine Learning

• String processing is extremely important in AI.
• Examples include:
• Natural Language Processing
• "Artificial intelligence is transforming industries."
• can be processed into:

• Applications
• Strings are used in:
• Text classification
• Sentiment analysis
• Chatbots
• Search engines
• Document processing
• Named Entity Recognition
• Tokenization
• Text embeddings
• Large Language Models
• Email analysis
• Resume processing

String processing is therefore an important foundation for NLP and Generative AI.

4.3.42Important String Interview Problems

Beginner

• Reverse a string
• Check palindrome
• Count characters
• Count vowels
• Count words
• Convert uppercase to lowercase
• Remove spaces
• Find string length
• Find character frequency
• Remove duplicate characters

Intermediate

• Check anagrams
• First non-repeating character
• Reverse words
• Longest common prefix
• Check string rotation
• Longest substring without repeating characters
• Count substring occurrences
• Compress a string
• Group anagrams
• Validate parentheses

Advanced

• KMP string matching
• Rabin-Karp
• Longest palindromic substring
• Longest palindromic subsequence
• Minimum window substring
• Edit distance
• Word Break
• Regular expression matching
• Implement Trie
• Word Search

4.3.43Key Takeaways

Remember these important concepts:

String indexing → O(1)

String traversal → O(n)

String slicing → O(k)

String reversal → O(n)

Character frequency → O(n)

Palindrome check → O(n)

Anagram using sorting → O(n log n)

Anagram using hashing → O(n) average

Longest unique substring → O(n) using sliding window

KMP string matching → O(n + m)

String construction → Prefer list + join for many pieces

The most important concepts to master from this section are string immutability, indexing, slicing, frequency counting, palindrome checking, anagrams, substring vs subsequence, two pointers, sliding window, and string matching. These concepts will be reused extensively in later sections such as Hash Tables, Recursion, Searching, Sliding Window, Two Pointers, Trie, Dynamic Programming, and Coding Interview Practice.

A Linked List is a linear data structure in which elements are stored inside individual nodes, and each node contains a reference to another node.

Unlike arrays, linked-list elements are not required to be stored next to each other in memory.

A simple singly linked list looks like this:

↑

Head

• Each node contains:
• Data — the value stored in the node.
• Next — a reference to the next node.

4.4.1Why Linked Lists?

Arrays provide very fast random access:

array[index] → O(1)

However, inserting or deleting elements near the beginning or middle can require shifting many elements.

• Linked lists solve this problem differently.
• For example:
• 10 → 20 → 40

To insert 30 between 20 and 40, we can change references:

10 → 20 → 30 → 40

No shifting of all subsequent elements is required.

This makes linked lists particularly useful when frequent insertions and deletions are required.

4.4.2Structure of a Node

A singly linked-list node can be represented as:

• Node
• ├── data
• └── next
• In Python:

class Node:
    def __init__(self, data):
        self.data = data

• self.next = None
• Creating a node:
• node = Node(10)

print(node.data)
print(node.next)

Output:

10

None

4.4.3Creating a Simple Linked List

We can manually connect nodes:

class Node:
    def __init__(self, data):
        self.data = data

• self.next = None
• first = Node(10)
• second = Node(20)
• third = Node(30)
• first.next = second
• second.next = third
• The structure becomes:
• first

↓

The first node is called the head.

4.4.4Head of a Linked List

• The head is a reference to the first node.
• head = first
• Conceptually:
• head

↓

• 10 → 20 → 30 → None
• If the linked list is empty:
• head = None
• The list is:
• None

4.4.5Traversing a Linked List

Unlike arrays, we cannot directly access a linked-list element by index.

We start at the head and follow next references.

def print_list(head):
current = head
while current is not None:
print(current.data)
current = current.next

• For:
• 10 → 20 → 30 → None
• the output is:
• 10
• 20
• 30
• Time complexity:

O(n)

4.4.6Creating a LinkedList Class

A better implementation is to create a class representing the entire list.

class Node:
    def __init__(self, data):
        self.data = data

self.next = None

class LinkedList:
    def __init__(self):
        self.head = None

• Now:
• linked_list = LinkedList()
• Initially:
• head → None

4.4.7Inserting at the Beginning

Suppose we have:

• 20 → 30 → 40
• and want to insert 10 at the beginning.
• We create a new node:
• 10

Then point it to the current head:

10 → 20 → 30 → 40

Implementation:

def insert_at_beginning(self, data):
new_node = Node(data)

• new_node.next = self.head
• self.head = new_node
• Time complexity:

O(1)

This is one of the major advantages of linked lists.

4.4.8Inserting at the End

• Suppose:
• 10 → 20 → 30
• We want:
• 10 → 20 → 30 → 40

We need to traverse to the last node.

def insert_at_end(self, data):
    new_node = Node(data)
    if self.head is None:
        self.head = new_node

return

current = self.head
while current.next is not None:
current = current.next

• current.next = new_node
• Without a tail pointer:
• Time = O(n)

If the list maintains a tail reference, insertion at the end can be:

O(1)

4.4.9Searching a Linked List

To find a value, traverse the list.

def search(self, target):
current = self.head
while current is not None:
if current.data == target:
return True
current = current.next
return False

Complexity:

Best Case = O(1)

Worst Case = O(n)

Space = O(1)

4.4.10Deleting the First Node

• Suppose:
• 10 → 20 → 30
• To remove 10:
• 20 → 30
• We simply move the head:
• self.head = self.head.next
• Complexity:

O(1)

4.4.11Deleting a Node by Value

• Suppose:
• 10 → 20 → 30 → 40
• and we want to delete 30.

We need to find the node before it:

20

Then change:

• 20.next
• from:
• 30
• to:
• 40
• Implementation:

def delete(self, target):
    if self.head is None:
        return

if self.head.data == target:
    self.head = self.head.next

return

current = self.head
while current.next is not None:
    if current.next.data == target:
        current.next = current.next.next

return

current = current.next

Worst-case complexity:

Time = O(n)

4.4.12Linked List Complexity

• * Without an appropriate tail pointer.
• The key difference from arrays is:
• Array:
• Random access → O(1)
• Linked List:
• Random access → O(n)

4.4.13Types of Linked Lists

• There are three major types:
• Singly Linked List
• Doubly Linked List
• Circular Linked List

4.4.14Singly Linked List

• Each node contains:
• Data
• Next
• Structure:
• 10 → 20 → 30 → 40 → None

Traversal is normally possible only in the forward direction.

Python implementation:

class Node:
    def __init__(self, data):
        self.data = data

self.next = None

4.4.15Doubly Linked List

A doubly linked list contains two references in each node:

• Previous
• Data
• Next
• Structure:
• None ← 10 ⇄ 20 ⇄ 30 → None
• A node can move:
• Forward
• Backward
• Node implementation:

class Node:
    def __init__(self, data):
        self.data = data

self.prev = None

self.next = None

4.4.16Advantages of Doubly Linked Lists

• Doubly linked lists provide:
• Forward traversal
• Backward traversal
• Efficient deletion when the target node is already known
• Convenient insertion before or after a node

However, every node requires an additional prev reference.

Therefore, memory usage is higher than a singly linked list.

4.4.17Circular Linked List

• In a circular linked list, the last node points back to the first node.
• Instead of:
• 10 → 20 → 30 → None
• we have:
• 10 → 20 → 30

↑ ↓

└─────────┘

The last node's next points to the head.

4.4.18Circular Singly Linked List

Example:

10 → 20 → 30

↑ ↓

└─────────┘

• The structure can be useful for problems involving repeated cycles.
• Examples include:
• Round-robin scheduling
• Circular buffers
• Repeating processes
• Multiplayer turn systems

4.4.19Circular Doubly Linked List

• A circular doubly linked list combines both concepts.
• Each node contains:
• prev
• data
• next
• and:
• head.prev → tail
• tail.next → head

This allows circular traversal in both directions.

4.4.20Array vs Linked List

The choice depends on the problem.

4.4.21Reversing a Linked List

• Reversing a linked list is one of the most important interview problems.
• Given:
• 10 → 20 → 30 → None
• we want:
• 30 → 20 → 10 → None
• The iterative solution uses three references:
• previous
• current
• next
• Implementation:

def reverse(self):
previous = None
current = self.head
while current is not None:
next_node = current.next

current.next = previous

previous = current

current = next_node

self.head = previous

Complexity:

Time = O(n)

Space = O(1)

This is an essential DSA pattern.

4.4.22Understanding Reversal

• Suppose:
• 10 → 20 → 30 → None
• Initially:
• previous = None

current  = 10

First iteration:

None ← 10 20 → 30

↑

previous

Next:

None ← 10 ← 20 30

↑

• previous
• Finally:
• None ← 10 ← 20 ← 30

↑

• previous
• Then:
• head = previous
• Result:
• 30 → 20 → 10 → None

4.4.23Recursive Reversal

A linked list can also be reversed recursively.

def reverse_recursive(self, node):
if node is None or node.next is None:
return node
new_head = self.reverse_recursive(node.next)

node.next.next = node

node.next = None

return new_head

The recursive approach has:

Time = O(n)

Space = O(n)

because of the recursion call stack.

The iterative approach is usually preferred when constant auxiliary space is desired.

4.4.24Finding the Middle Node

• A classic linked-list problem is finding the middle element.
• Suppose:
• 10 → 20 → 30 → 40 → 50
• The middle is:
• 30

A very useful technique is the slow and fast pointer technique.

def find_middle(head):
slow = head
fast = head
while fast is not None and fast.next is not None:
slow = slow.next
fast = fast.next.next
return slow

• The slow pointer moves one step while the fast pointer moves two.
• When the fast pointer reaches the end, the slow pointer is at the middle.
• Complexity:

Time = O(n)

Space = O(1)

4.4.25Detecting a Cycle

Consider:

10 → 20 → 30 → 40

↑ ↓

└────┘

The linked list contains a cycle.

The Floyd Cycle Detection Algorithm uses two pointers:

Slow pointer moves one step.

Fast pointer moves two steps.

def has_cycle(head):
slow = head
fast = head
while fast is not None and fast.next is not None:
slow = slow.next
fast = fast.next.next
if slow == fast:
return True
return False

Complexity:

Time = O(n)

Space = O(1)

This is one of the most important linked-list interview techniques.

4.4.26Finding the Nth Node from the End

Suppose:

10 → 20 → 30 → 40 → 50

We want the second node from the end:

40

Use two pointers.

def nth_from_end(head, n):
first = head
second = head
for _ in range(n):
if first is None:
return None
first = first.next
while first is not None:
first = first.next
second = second.next
return second

The two pointers maintain a gap of n nodes.

Complexity:

Time = O(n)

Space = O(1)

4.4.27Merging Two Sorted Linked Lists

• Suppose we have:
• List 1:
• 1 → 3 → 5
• List 2:
• 2 → 4 → 6
• The merged list is:

1 → 2 → 3 → 4 → 5 → 6

Implementation:

def merge_lists(a, b):
    dummy = Node(0)
    current = dummy
    while a is not None and b is not None:
        if a.data <= b.data:
            current.next = a

a = a.next
else:
    current.next = b

b = b.next
current = current.next
if a is not None:
    current.next = a

else:
    current.next = b

return dummy.next

If the lists contain n and m nodes:

Time = O(n + m)

Space = O(1)

assuming no new nodes are created for the merged sequence.

4.4.28Removing Duplicates

• Consider:
• 10 → 20 → 20 → 30 → 30
• We want:
• 10 → 20 → 30
• For a sorted linked list:

def remove_duplicates(head):
    current = head
    while current is not None and current.next is not None:
        if current.data == current.next.data:
            current.next = current.next.next

else:
current = current.next
return head

Because the list is sorted, duplicate values are adjacent.

Complexity:

Time = O(n)

Space = O(1)

4.4.29Intersection of Two Linked Lists

Suppose two linked lists eventually share the same node:

List A:

1 → 2 → 3

\

7 → 8

List B:

4 → 5 → 6 ─┘

The intersection begins at:

7

A useful two-pointer technique allows us to find the intersection in:

Time = O(n + m)

Space = O(1)

The key idea is that each pointer switches to the other list after reaching the end, equalizing the distance traveled.

4.4.30Palindrome Linked List

A linked list can be checked for palindrome structure.

Example:

• 1 → 2 → 3 → 2 → 1
• A common efficient approach is:
• Find the middle.
• Reverse the second half.
• Compare both halves.
• Optionally restore the list.
• This combines several important techniques:
• Slow/Fast Pointers

+

Linked List Reversal

+

Two Pointers

Typical complexity:

Time = O(n)

Space = O(1)

4.4.31Dummy Node Technique

A dummy node is an extra node placed before the actual head.

Example:

• dummy → 10 → 20 → 30
• It simplifies operations involving the first node.
• For example:
• dummy = Node(0)
• dummy.next = head
• Then:
• dummy.next
• represents the actual head.
• Dummy nodes are particularly useful in:
• Merging lists
• Removing nodes
• Inserting nodes
• Partitioning lists
• They reduce special-case logic.

4.4.32Common Linked List Interview Patterns

• Pattern 1 — Two Pointers
• Used for:
• Finding middle
• Detecting cycles
• Finding nth node from end
• Comparing sections
• Pattern 2 — Reversal
• Used for:
• Reversing entire list
• Reversing a portion
• Palindrome problems
• Pattern 3 — Dummy Node
• Used for:
• Merging
• Deleting
• Inserting
• Partitioning
• Pattern 4 — Fast and Slow Pointers
• Used for:
• Middle node
• Cycle detection
• Cycle entry

These patterns are more important than simply memorizing linked-list methods.

4.4.33Advantages of Linked Lists

1. Dynamic Size

A linked list can grow and shrink naturally.

2. Efficient Insertion

Insertion at the beginning is:

O(1)

3. Efficient Deletion

Deletion at the beginning is:

O(1)

4. No Element Shifting

Unlike arrays, linked lists don't need to shift every subsequent element after an insertion or deletion.

5. Useful Building Block

Linked lists can be used to implement:

• Stacks
• Queues
• Hash-table buckets
• Graph adjacency structures

4.4.34Disadvantages of Linked Lists

1. Slow Random Access

Accessing the nth node requires traversal:

O(n)

2. Extra Memory

• Each node needs references such as:
• next
• or:
• prev + next

3. Poor Cache Locality

Nodes may be located in different memory locations.

4. More Complex Implementation

Pointers/references must be maintained carefully.

5. Binary Search Is Not Efficient

Although a linked list can theoretically contain sorted values, finding the middle repeatedly requires traversal, so binary search does not provide the same practical benefit as it does with arrays.

4.4.35Linked List vs Array

A useful way to remember the difference:

ARRAY

↑

• Fast random access
• versus:
• LINKED LIST

↑

• Head
• Array
• Best when you need:
• Fast indexing
• Frequent reads
• Good cache locality
• Efficient sorting/searching
• Linked List
• Best when you need:
• Frequent insertion/deletion
• Sequential processing
• Flexible node-based structures

4.4.36Linked Lists in Real-World Systems

• Linked-list concepts appear in many systems.
• Examples include:
• Operating system scheduling
• Memory management
• Browser navigation structures
• Undo/redo systems
• Music playlists
• Hash-table chaining
• Graph representations
• LRU cache implementations

A particularly important application is the LRU Cache, which commonly combines:

Hash Map + Doubly Linked List

This combination allows efficient lookup and ordering.

4.4.37Important Linked List Problems

Beginner

• Create a linked list.
• Traverse a linked list.
• Insert at beginning.
• Insert at end.
• Insert at a given position.
• Delete first node.
• Delete last node.
• Delete by value.
• Search for a value.
• Count nodes.

Intermediate

• Reverse a linked list.
• Find the middle node.
• Find nth node from the end.
• Detect a cycle.
• Remove duplicates.
• Merge two sorted lists.
• Find intersection of two lists.
• Check palindrome.
• Remove nth node from the end.
• Partition a linked list.

Advanced

• Find the start of a cycle.
• Reverse nodes in groups of k.
• Sort a linked list.
• Merge k sorted linked lists.
• Copy a list with random pointers.
• Flatten a multilevel linked list.
• Implement an LRU Cache.
• Rotate a linked list.
• Add two numbers represented by linked lists.
• Reorder a linked list.

4.4.38Complexity Summary

4.4.39Key Takeaways

The most important concepts to remember are:

• Node
• ├── Data
• └── Next
• Singly Linked List
• 10 → 20 → 30 → None
• Doubly Linked List
• None ← 10 ⇄ 20 ⇄ 30 → None
• Circular Linked List
• 10 → 20 → 30

↑ ↓

└─────────┘

And the most important interview techniques are:

• Two Pointers
• Fast & Slow Pointers
• Linked List Reversal
• Dummy Node
• Cycle Detection
• Merge Sorted Lists
• Most important complexities

Access by index → O(n)

Search → O(n)

Insert at head → O(1)

Delete at head → O(1)

Reverse → O(n)

Find middle → O(n)

Detect cycle → O(n)

The central idea is:

Arrays are optimized for fast random access, while linked lists are optimized for efficient insertion and deletion when the relevant node position is already known.

Understanding this tradeoff is essential before moving to 4.5 Stacks, because stacks can be implemented efficiently using either arrays or linked lists.

A Stack is a linear data structure that follows the LIFO (Last In, First Out) principle.

This means the element added last is the element removed first.

A real-world example is a stack of plates:

┌───────┐

│ Plate │ ← Last added / First removed

├───────┤

│ Plate │

├───────┤

│ Plate │

├───────┤

│ Plate │ ← First added / Last removed

└───────┘

• If we add:
• 10 → 20 → 30
• the stack becomes:

20

10

When we remove an element, 30 is removed first.

4.5.1LIFO Principle

LIFO stands for:

Last In, First Out

Example:

• Push 10
• Push 20
• Push 30
• Stack:
• TOP → 30
• 20
• 10
• Now:
• Pop()
• returns:
• 30
• The stack becomes:
• TOP → 20
• 10

4.5.2Basic Stack Operations

A stack typically supports these operations:

The top is the only end from which normal stack operations are performed.

4.5.3Push Operation

Push adds an element to the top of the stack.

Starting stack:

10

Push 30:

• 20
• 10
• In Python:

stack = []

• stack.append(10)
• stack.append(20)
• stack.append(30)

print(stack)

Output:

• The right side represents the top.
• Time complexity:
• O(1) amortized

4.5.4Pop Operation

Pop removes the top element.

stack = [10, 20, 30]
value = stack.pop()
print(value)
print(stack)

Output:

30

Time complexity:

O(1)

4.5.5Peek Operation

Peek returns the top element without removing it.

stack = [10, 20, 30]
print(stack[-1])

Output:

30

The stack remains:

Complexity:

O(1)

4.5.6Checking Whether a Stack Is Empty

stack = []
if not stack:
print("Stack is empty")

Another approach:

if len(stack) == 0:
print("Stack is empty")

Complexity:

O(1)

4.5.7Stack Using Python List

The simplest implementation is:

stack = []

• stack.append(10)
• stack.append(20)
• stack.append(30)

print(stack.pop())
print(stack[-1])

Output:

30

20

Python's list provides the required operations efficiently when we use the end of the list as the stack top.

• Avoid using:
• stack.insert(0, value)
• stack.pop(0)

because operations at the beginning of a Python list require shifting elements and are generally O(n).

4.5.8Implementing a Stack Class

We can create our own stack abstraction:

class Stack:
    def __init__(self):
        self.items = []

def push(self, value):
    self.items.append(value)

def pop(self):
if self.is_empty():
return None
return self.items.pop()
def peek(self):
if self.is_empty():
return None
return self.items[-1]
def is_empty(self):
return len(self.items) == 0
def size(self):
return len(self.items)

• Usage:
• stack = Stack()
• stack.push(10)
• stack.push(20)
• stack.push(30)

print(stack.peek())
print(stack.pop())
print(stack.size())

Output:

• 30
• 30
• 2

4.5.9Stack Using Linked List

• A stack can also be implemented using a linked list.
• Consider:
• TOP

↓

• 30 → 20 → 10 → None
• The head of the linked list acts as the stack top.
• Node

class Node:
    def __init__(self, data):
        self.data = data

self.next = None

Stack

class Stack:
    def __init__(self):
        self.top = None

def push(self, data):
new_node = Node(data)

new_node.next = self.top

self.top = new_node

def pop(self):
if self.top is None:
return None
value = self.top.data

self.top = self.top.next

return value
def peek(self):
if self.top is None:
return None
return self.top.data

Both push() and pop() operate at the head.

Therefore:

Push → O(1)

Pop → O(1)

Peek → O(1)

4.5.10Array-Based Stack vs Linked-List Stack

For most Python applications, a list is the simplest choice.

4.5.11Stack Overflow

• In a fixed-size stack, stack overflow occurs when we try to push an element into a full stack.
• For example:
• Maximum capacity = 3

• Trying:
• push(40)
• causes overflow.

With Python's dynamically growing list, the concept is different: memory exhaustion rather than a fixed stack capacity is the practical limitation.

4.5.12Stack Underflow

Stack underflow occurs when we try to remove an element from an empty stack.

Example:

stack = []

• stack.pop()
• Python raises an IndexError.
• A custom implementation should usually check:

if not stack:
return None

before popping.

4.5.13Stack Complexity

The key advantage of a stack is that its primary operations are constant time.

4.5.14Applications of Stacks

• Stacks are used extensively in computer science.
• Important applications include:
• Function calls
• Recursion
• Undo/Redo
• Browser history
• Expression evaluation
• Parentheses matching
• Syntax parsing
• Depth-First Search
• Backtracking
• Monotonic stack problems

4.5.15Call Stack

One of the most important applications of stacks is function execution.

Consider:

def first():
    second()

def second():
    third()

def third():
print("Hello")

first()

The call stack conceptually becomes:

• second()
• first()
• main()
• When third() finishes:
• third() → removed
• Then:
• second() → removed
• Then:
• first() → removed

This is why recursion is closely connected to stacks.

4.5.16Stack and Recursion

Consider:

def countdown(n):
    if n == 0:
        return

print(n)

• countdown(n - 1)
• Calling:
• countdown(3)
• creates:
• countdown(3)
• countdown(2)
• countdown(1)
• countdown(0)

These calls are stored on the call stack.

Therefore, recursive algorithms can consume O(n) stack space when recursion depth is n.

4.5.17Balanced Parentheses

One of the most common stack problems is checking whether parentheses are balanced.

For example:

( )

( [ ] )

{ [ ( ) ] }

are valid.

But:

( ]

( [ )

{ [ } ]

are invalid.

A stack can solve this efficiently.

def is_balanced(expression):
    stack = []
    pairs = {
        ")": "(",
        "]": "[",
        "}": "{"
    }

for character in expression:
    if character in "([{":
        stack.append(character)
        elif character in ")]}":
        if not stack or stack.pop() != pairs[character]:
            return False
            return not stack

Example:

print(is_balanced("{[()]}"))

Output:

True

Complexity:

Time = O(n)

Space = O(n)

4.5.18Why a Stack Works for Parentheses

Consider:

{ [ ( ) ] }

• Process:
• { → push
• [ → push
• ( → push

) → pop (

] → pop [

} → pop {

Every closing bracket must match the most recently opened bracket.

That is exactly the LIFO behavior of a stack.

4.5.19Reverse a String Using a Stack

A stack can reverse a string.

def reverse_string(text):
    stack = []
    for character in text:
        stack.append(character)

result = []
while stack:
    result.append(stack.pop())

return "".join(result)

Example:

print(reverse_string("Python"))

Output:

nohtyP

Complexity:

Time = O(n)

Space = O(n)

4.5.20Evaluate Postfix Expressions

• Stacks are widely used for evaluating mathematical expressions.
• Consider postfix:
• 2 3 + 4 *
• This represents:

(2 + 3) * 4

Algorithm:

def evaluate_postfix(expression):
    stack = []
    for token in expression.split():
        if token.isdigit():
            stack.append(int(token))

else:
    right = stack.pop()
    left = stack.pop()
    if token == "+":
        stack.append(left + right)

elif token == "-":
    stack.append(left - right)

elif token == "*":
    stack.append(left * right)

elif token == "/":
    stack.append(left / right)

return stack.pop()

Example:

print(evaluate_postfix("2 3 + 4 *"))

Output:

20

4.5.21Infix, Prefix and Postfix

• There are three common expression notations.
• Infix
• Operator appears between operands:
• A + B
• Prefix
• Operator appears before operands:
• + A B
• Postfix
• Operator appears after operands:
• A B +

Stacks are commonly used to convert and evaluate these expressions.

4.5.22Infix to Postfix

• Consider:
• A + B * C
• Because multiplication has higher precedence:

A + (B * C)

Postfix representation:

A B C * +

A stack can be used to manage operators and their precedence.

This is a classic application of stacks in compiler and expression-processing algorithms.

4.5.23Undo and Redo

• Text editors can use stacks for undo operations.
• Suppose the user performs:
• Type A
• Type B
• Type C
• Undo stack:

• B
• A
• Press Undo:
• C
• is removed.
• Another Undo removes:
• B

Redo functionality can use a second stack:

• Undo Stack
• Redo Stack
• This creates a common two-stack design.

4.5.24Browser History

Browser navigation can also be modeled using stacks.

For example:

• Going backward removes the most recent page from the history stack.
• A forward stack can store pages that were backed out of.
• Conceptually:
• Back Stack
• Forward Stack

4.5.25Depth-First Search

DFS (Depth-First Search) uses stack behavior.

A graph traversal can be implemented recursively:

def dfs(node):
    if node is None:
        return

visited.add(node)

for neighbor in graph[node]:
    if neighbor not in visited:
        dfs(neighbor)

The recursion call stack effectively provides stack behavior.

DFS can also be implemented explicitly:

def dfs(graph, start):
    stack = [start]
    visited = set()
    while stack:
        node = stack.pop()
        if node in visited:
            continue

visited.add(node)

for neighbor in graph[node]:
    if neighbor not in visited:
        stack.append(neighbor)

return visited

This connection becomes important in Section 4.13 – Graph Traversal.

4.5.26Backtracking

• Backtracking algorithms frequently use stack-like behavior.
• Examples include:
• Maze solving
• Sudoku
• N-Queens
• Permutations
• Combination generation
• A typical pattern is:

The recursive call stack stores the current decision path.

4.5.27Monotonic Stack

A monotonic stack is a special stack that maintains elements in increasing or decreasing order.

It is useful for problems such as:

• Next Greater Element
• Next Smaller Element
• Daily Temperatures
• Largest Rectangle in Histogram
• Stock Span
• For example, in Next Greater Element:

Input:

We want to find the first larger element to the right of each value.

A monotonic stack can solve many such problems in:

O(n)

instead of the brute-force:

O(n²)

This is an important advanced interview pattern.

4.5.28Next Greater Element

Consider:

The next greater element for each value is:

2 → 5

1 → 5

5 → -1

3 → 4

4 → -1

Result:

A monotonic stack solution:

def next_greater(numbers):
result = [-1] * len(numbers)
stack = []
for i, number in enumerate(numbers):
while stack and numbers[stack[-1]] < number:
index = stack.pop()

result[index] = number

stack.append(i)

return result

Complexity:

Time = O(n)

Space = O(n)

Although there is a nested-looking while loop, each element is pushed and popped at most once.

4.5.29Important Insight About Nested Loops

Consider:

while stack and numbers[stack[-1]] < number:
    stack.pop()

It may look like an O(n²) algorithm because of the nested loop structure.

However, each element can be:

Pushed → Once

Popped → Once

Therefore, across the entire algorithm:

Total stack operations = O(n)

So the overall time complexity is:

O(n)

This is an important example of amortized analysis.

4.5.30Stack vs Queue

Stacks and queues are both linear data structures, but their ordering principles differ.

Example stack:

Push → 10 → 20 → 30

Pop → 30

• Example queue:
• Enqueue → 10 → 20 → 30
• Dequeue → 10

4.5.31Stack vs Array

A stack is an abstract data structure, while an array/list is a concrete storage structure.

For example:

↓

Python List

or:

• The stack defines the behavior:
• push
• pop
• peek

The underlying data structure determines how that behavior is implemented.

4.5.32Real-World Applications

• Stacks are used in:
• Function-call management
• Recursion
• Expression evaluation
• Compilers
• Syntax parsing
• Browser history
• Undo/redo
• DFS
• Backtracking
• Maze solving
• Parentheses validation
• Monotonic-stack problems
• Memory management

4.5.33Common Stack Interview Problems

Beginner

• Implement a stack.
• Push and pop elements.
• Implement peek.
• Check if stack is empty.
• Reverse a string.
• Check balanced parentheses.
• Implement stack using a linked list.

Intermediate

• Min Stack.
• Evaluate postfix expression.
• Infix to postfix conversion.
• Next Greater Element.
• Stock Span.
• Remove adjacent duplicates.
• Simplify a file path.
• Decode a string.

Advanced

• Largest Rectangle in Histogram.
• Maximal Rectangle.
• Daily Temperatures.
• Trapping Rain Water using a stack.
• Implement a queue using two stacks.
• Implement a stack using two queues.
• Design an expression evaluator.
• Basic Calculator.
• Online Stock Span.
• Asteroid Collision.

4.5.34Min Stack

A popular interview problem is designing a stack that supports:

• push()
• pop()
• top()
• get_min()
• all in:

O(1)

• A common solution maintains two stacks:
• Main Stack
• Min Stack

Example:

Main Stack Min Stack

30 30

20 20

40 20

10 10

The minimum value is always available at the top of the minimum stack.

4.5.35Implement Queue Using Two Stacks

A queue follows FIFO, while a stack follows LIFO.

We can implement a queue using two stacks:

Input Stack

• Output Stack
• When elements need to be removed, transfer elements from the input stack to the output stack.
• For example:

Input:

10 20 30

Transfer:

Output:

30 20 10

Now popping from the output stack gives:

10

which produces FIFO behavior.

This is a classic interview problem.

4.5.36Stack Complexity Summary

4.5.37Key Takeaways

• Remember the fundamental principle:
• LIFO
• Last In → First Out
• The three most important operations are:
• push() → Add to top

pop() → Remove from top

• peek() → View top
• Typical complexity:
• Push → O(1)

Pop → O(1)

• Peek → O(1)
• The most important applications are:
• Recursion
• Function Calls
• Undo/Redo
• Browser History
• Parentheses Matching
• Expression Evaluation
• DFS
• Backtracking
• Monotonic Stack

The most important interview patterns to master are:

Balanced Parentheses → Two Stacks → Fast Stack Operations → Monotonic Stack → Next Greater Element → Min Stack

Once stacks are understood, the next major linear data structure is 4.6 Queues, which reverses the ordering principle from LIFO to FIFO.

A Queue is a linear data structure that follows the FIFO (First In, First Out) principle.

This means the element that enters the queue first is the element that leaves first.

A real-world example is people waiting in a line:

First Person Last Person

↓ ↓

↑ ↑

FRONT REAR

If 10 entered first, it will be removed first.

4.6.1FIFO Principle

• FIFO stands for:
• First In, First Out
• Suppose we add:
• Enqueue 10
• Enqueue 20
• Enqueue 30
• The queue becomes:

FRONT REAR

↓ ↓

• Now:
• Dequeue()
• removes:
• 10
• The queue becomes:

FRONT REAR

↓ ↓

This is the fundamental difference between a queue and a stack.

4.6.2Queue vs Stack

Stack:

Push: 10 → 20 → 30

Pop: 30

• Queue:
• Enqueue: 10 → 20 → 30
• Dequeue: 10

4.6.3Basic Queue Operations

A queue normally supports:

4.6.4Enqueue

• Enqueue adds an element to the rear of the queue.
• Starting queue:
• FRONT

↓

↑

• REAR
• Enqueue 30:
• FRONT

↓

↑

REAR

The new element is always added at the rear.

4.6.5Dequeue

Dequeue removes the element from the front.

FRONT

↓

• After:
• dequeue()
• we get:
• 10
• and the queue becomes:
• FRONT

↓

4.6.6Queue Using Python deque

The recommended Python implementation is collections.deque.

from collections import deque
queue = deque()

• queue.append(10)
• queue.append(20)
• queue.append(30)

print(queue)

Output:

deque([10, 20, 30])

Remove from the front:

value = queue.popleft()
print(value)

Output:

• 10
• Now:
• deque([20, 30])
• Both:
• queue.append(value)
• queue.popleft()

are designed for efficient operations at their respective ends.

4.6.7Why Not Use a Python List?

You can technically implement a queue with:

queue = []

• queue.append(10)
• queue.append(20)
• queue.append(30)
• queue.pop(0)

However:

• queue.pop(0)
• requires shifting the remaining elements.
• Its complexity is generally:

O(n)

For a queue, prefer:

from collections import deque
queue = deque()

• queue.append(10)
• queue.popleft()
• This provides efficient front removal.

4.6.8Queue Implementation Using a Class

We can create a simple queue:

from collections import deque
class Queue:
    def __init__(self):
        self.items = deque()

def enqueue(self, value):
    self.items.append(value)

def dequeue(self):
if self.is_empty():
return None
return self.items.popleft()
def front(self):
if self.is_empty():
return None
return self.items[0]
def is_empty(self):
return len(self.items) == 0
def size(self):
return len(self.items)

• Usage:
• queue = Queue()
• queue.enqueue(10)
• queue.enqueue(20)
• queue.enqueue(30)

print(queue.front())
print(queue.dequeue())
print(queue.size())

Output:

• 10
• 10
• 2

4.6.9Queue Using a Linked List

A queue can also be implemented using a linked list.

The ideal structure maintains two references:

FRONT REAR

↓ ↓

[10] → [20] → [30] → None

• The front is used for deletion.
• The rear is used for insertion.
• This allows:
• Enqueue → O(1)
• Dequeue → O(1)

4.6.10Node Implementation

class Node:
    def __init__(self, data):
        self.data = data

self.next = None

Queue:

class Queue:
    def __init__(self):
        self.front = None

self.rear = None

def enqueue(self, data):
    new_node = Node(data)
    if self.rear is None:
        self.front = self.rear = new_node

• return
• self.rear.next = new_node
• self.rear = new_node

def dequeue(self):
if self.front is None:
return None
value = self.front.data

self.front = self.front.next

if self.front is None:
    self.rear = None

return value

4.6.11Queue Complexity

With a linked list containing both front and rear references:

This is an efficient queue implementation.

4.6.12Queue Overflow

In a fixed-size queue, overflow occurs when the queue is full and another element is inserted.

For example:

Capacity = 3

• Trying:
• enqueue(40)
• causes overflow.

Dynamic implementations such as Python's deque grow as needed, subject to available memory.

4.6.13Queue Underflow

Underflow occurs when we attempt to remove an element from an empty queue.

For example:

from collections import deque
queue = deque()

• queue.popleft()
• raises an IndexError.
• A custom queue can safely check:

if not queue:
return None

4.6.14Types of Queues

• The main types of queues are:
• Simple Queue
• Circular Queue
• Priority Queue
• Deque (Double-Ended Queue)

Each type is useful for different problems.

4.6.15Simple Queue

• A simple queue follows:
• FIFO
• Elements are:
• Added at the rear.
• Removed from the front.

Example:

FRONT REAR

↓ ↓

• 10 → 20 → 30 → 40
• Dequeue removes:
• 10

4.6.16Circular Queue

A Circular Queue connects the end of the queue back to the beginning.

Conceptually:

┌─────────────────┐

↓ │

↑ │

└───────────────────────┘

This allows unused positions at the beginning of a fixed-size array to be reused.

4.6.17Why Circular Queues?

Consider a fixed-size queue with capacity 5:

• Remove:
• 10
• 20
• We now have:

• There is free space at the beginning.
• A simple linear queue might incorrectly appear full if the rear is already at the end.
• A circular queue reuses those positions.

This improves memory utilization.

4.6.18Circular Queue Implementation

• A circular queue can be implemented using an array and modular arithmetic.
• The key formula is:
• rear = (rear + 1) % capacity
• Similarly:
• front = (front + 1) % capacity

Example:

class CircularQueue:
    def __init__(self, capacity):
        self.queue = [None] * capacity

• self.capacity = capacity
• self.front = 0
• self.rear = 0
• self.size = 0

The modulo operator allows indexes to wrap around to the beginning.

4.6.19Priority Queue

• A Priority Queue removes elements based on priority rather than simply insertion order.
• For example:
• Patient A → Priority 2
• Patient B → Priority 5
• Patient C → Priority 1
• If larger numbers indicate higher priority:
• Patient B

is processed first even though it may have arrived later.

Priority queues are commonly implemented using heaps, which are covered in Section 4.11.

4.6.20Python Priority Queue

Python provides heapq:

import heapq
queue = []

• heapq.heappush(queue, (2, "Patient A"))
• heapq.heappush(queue, (1, "Patient B"))
• heapq.heappush(queue, (3, "Patient C"))

print(heapq.heappop(queue))

Output:

(1, 'Patient B')

The smallest priority value is returned first.

4.6.21Deque

Deque stands for:

Double-Ended Queue

It allows insertion and removal from both ends.

FRONT REAR

↓ ↓

Python provides:

from collections import deque

Example:

• queue = deque([20, 30])
• queue.appendleft(10)
• queue.append(40)

print(queue)

Output:

• deque([10, 20, 30, 40])
• Remove from the left:
• queue.popleft()
• Remove from the right:
• queue.pop()

4.6.22Deque Complexity

Typical deque operations at either end are:

appendleft() → O(1)

append() → O(1)

popleft() → O(1)

pop() → O(1)

This makes deque very useful for queue and sliding-window problems.

4.6.23Queue Applications

• Queues are widely used in computer science.
• Important applications include:
• CPU scheduling
• Printer scheduling
• Network packet processing
• Customer-service systems
• Breadth-First Search
• Task scheduling
• Message queues
• Producer-consumer systems
• Buffer management
• Web server request handling

4.6.24Queue in CPU Scheduling

Suppose several processes are waiting for CPU time:

• P1 → P2 → P3 → P4
• A scheduling algorithm can process them in queue order.
• For Round Robin scheduling, processes repeatedly receive a fixed time slice.
• Conceptually:
• P1 → P2 → P3 → P4

↑ ↓

└─────────────────┘

This is closely related to circular queues.

4.6.25Queue in Networking

• Network systems often process packets in the order they arrive.
• For example:
• Packet 1
• Packet 2
• Packet 3
• Packet 4
• A queue can temporarily store packets:
• Incoming packets

↓

↓

Network processing

This allows producers and consumers to operate at different speeds.

4.6.26Queue in Message Processing

Modern distributed systems commonly use message queues.

Conceptually:

For example:

• Queues provide buffering between components.
• They can help with:
• Asynchronous processing
• Load balancing
• Fault tolerance
• Traffic spikes
• Background jobs

4.6.27BFS Uses a Queue

• One of the most important DSA applications of queues is Breadth-First Search (BFS).
• Consider a graph:
• A

/ \

B C

/ \ \

D E F

• BFS visits nodes level by level:
• A
• B C
• D E F
• A queue stores nodes waiting to be processed.
• Conceptually:
• Queue:

Process A

Queue:

Process B

Queue:

Process C

Queue:

This is why queues are fundamental to BFS.

4.6.28BFS Example

from collections import deque
def bfs(graph, start):
    queue = deque([start])
    visited = {start}
    while queue:
        node = queue.popleft()
        print(node)
        for neighbor in graph[node]:
            if neighbor not in visited:
                visited.add(neighbor)

• queue.append(neighbor)
• For a graph with:
• V = vertices
• E = edges
• BFS typically has:

Time = O(V + E)

Space = O(V)

4.6.29Producer-Consumer Problem

The Producer-Consumer model is another important application.

Producer

↓

↓

• Consumer
• The producer generates items.
• The consumer processes them.
• If the producer is faster:
• Queue grows
• If the consumer is faster:
• Queue becomes empty

A queue acts as a buffer between the two.

Python provides queue.Queue for thread-safe producer-consumer scenarios.

4.6.30Queue vs Deque

A deque is more flexible because it supports both ends.

4.6.31Queue vs Priority Queue

• Normal queue:
• A → B → C
• Dequeue:
• A
• Priority queue:
• A(priority 2)
• B(priority 1)
• C(priority 3)
• Remove:
• B

because it has the highest priority under the chosen priority convention.

4.6.32Sliding Window and Queues

Queues and deques are heavily used in sliding window algorithms.

Suppose we want the maximum value in every window of size k:

For:

k = 3

the windows are:

[1, 3, -1] → 3

[3, -1, -3] → 3

[-1, -3, 5] → 5

...

A monotonic deque can solve this efficiently in:

O(n)

This will become especially important in Section 4.21 Sliding Window.

4.6.33Queue Interview Problem: Implement Queue Using Stacks

• A common interview problem is:
• Implement a FIFO queue using only stacks.
• Use two stacks:
• Input Stack
• Output Stack
• Suppose:
• enqueue(10)
• enqueue(20)
• enqueue(30)
• Input stack:

• 20
• 10
• Transfer to output:

20

30

Now popping from the output stack produces:

10

which gives FIFO behavior.

4.6.34Queue Interview Problem: Generate Binary Numbers

For a given n, generate binary numbers:

• 1
• 10
• 11
• 100
• 101

...

A queue can be used to generate them systematically.

This demonstrates that queues are useful beyond simple insertion and deletion.

4.6.35Queue Interview Problem: First Non-Repeating Character

• A queue can help track characters in the order they appeared.
• For example:
• a a b c
• A frequency map stores counts, while a queue stores candidate characters.
• This combination of:
• Queue + Hash Table
• is a common DSA pattern.

4.6.36Important Queue Patterns

Pattern 1 — BFS

Pattern 2 — Sliding Window

Pattern 3 — Producer-Consumer

Pattern 4 — Scheduling

Pattern 5 — Priority Processing

4.6.37Common Queue Interview Problems

Beginner

• Implement a queue.
• Enqueue elements.
• Dequeue elements.
• Implement front and rear.
• Check whether a queue is empty.
• Implement queue using a linked list.
• Implement circular queue.

Intermediate

• Implement a queue using two stacks.
• Implement a stack using two queues.
• Generate binary numbers using a queue.
• Reverse a queue.
• First non-repeating character in a stream.
• Number of recent requests.
• BFS traversal.
• Level-order traversal of a binary tree.

Advanced

• Sliding Window Maximum.
• Rotten Oranges.
• Shortest path in an unweighted graph.
• Course Schedule.
• Task scheduling.
• Design a priority queue.
• Design a thread-safe producer-consumer queue.
• Multi-source BFS problems.
• 0-1 BFS.

Implement an LRU Cache using a deque/hash-map combination.

4.6.38Queue Complexity Summary

4.6.39Python Queue Structures

Python provides several useful choices.

collections.deque

Best general-purpose choice for efficient operations at both ends:

from collections import deque
queue = deque()

queue.append(10)

queue.append(20)

print(queue.popleft())

queue.Queue

Useful for thread-safe producer-consumer scenarios:

from queue import Queue
q = Queue()

q.put(10)

q.put(20)

print(q.get())

heapq

Useful when elements need to be processed by priority:

import heapq
pq = []

heapq.heappush(pq, 10)

heapq.heappush(pq, 5)

print(heapq.heappop(pq))

Output:

5

This is a priority queue pattern rather than a normal FIFO queue.

4.6.40Real-World Example

• Consider an online food-ordering system.
• Orders arrive:
• Order 101
• Order 102
• Order 103
• Order 104

A normal processing queue might look like:

FRONT REAR

↓ ↓

• 101 → 102 → 103 → 104
• The kitchen processes:
• 101
• then:
• 102
• then:
• 103

This is FIFO.

If urgent orders need special treatment, a priority queue may be more appropriate.

4.6.41Key Differences to Remember

Stack

Queue

Priority Queue

Deque

Both ends

↕

Insert + Remove

4.6.42Key Takeaways

• The most important principle is:
• A queue follows FIFO — First In, First Out.
• Remember the fundamental operations:
• enqueue() → Add at rear
• dequeue() → Remove from front

peek() → View front

• Typical complexity:
• Enqueue → O(1)
• Dequeue → O(1)

Peek → O(1)

• The most important queue types are:
• Simple Queue
• Circular Queue
• Priority Queue
• Deque
• The most important applications are:
• BFS
• CPU Scheduling
• Task Scheduling
• Network Buffers
• Message Queues
• Producer-Consumer
• Sliding Window
• Level-Order Tree Traversal
• For Python, remember:

from collections import deque

• and prefer:
• queue.append(value)
• queue.popleft()

for a normal efficient FIFO queue.

The key interview patterns to master are BFS, circular queues, queue using two stacks, monotonic deque, sliding-window maximum, and producer-consumer problems.

A Hash Table is a data structure that stores data as key-value pairs and provides very fast average-case insertion, lookup, and deletion.

In Python, the built-in dictionary (dict) is a hash-table-based data structure.

For example:

student = {
    "name": "Sreehari",
    "age": 37,
    "course": "AI/ML"
}

Here:

Key → Value

-------------------------

"name" → "Sreehari"

"age" → 37

"course" → "AI/ML"

The key is used to efficiently locate its corresponding value.

4.7.1Why Hash Tables?

Suppose we have one million records and want to find a particular value.

With an unsorted array, we may need to search through many elements:

O(n)

A hash table can typically find the value in:

O(1) average

This makes hash tables extremely useful for:

• Fast lookups
• Frequency counting
• Duplicate detection
• Caching
• Indexing
• Database-like key-value access
• Graph algorithms
• Coding interview problems

4.7.2Hash Table Structure

Conceptually, a hash table looks like an array of buckets:

Index Bucket

-------------------------

0 ...

1 ...

2 ...

3 ...

4 ...

5 ...

6 ...

7 ...

A hash function converts a key into a value that determines where the key-value pair should be stored.

Conceptually:

For example:

4.7.3Hash Function

• A hash function converts a key into a numeric hash value.
• Conceptually:
• hash(key) → integer
• For example:
• hash("apple") → 123456...
• The actual value depends on the programming language and implementation.
• A good hash function should:
• Be deterministic for a given key during the relevant table operation.
• Distribute keys reasonably evenly.
• Be efficient to compute.
• Minimize collisions.

4.7.4Hashing

Hashing is the process of using a hash function to map a key to a location in a hash table.

Conceptually:

Key

│

▼

Hash Function

│

▼

Hash Value

│

▼

Bucket

For example:

Key = "Sreehari"

The exact bucket calculation depends on the implementation.

4.7.5Python Dictionary

Python's dictionary provides a convenient interface for hash-table operations.

student = {
    "name": "Sreehari",
    "age": 37,
    "city": "Hyderabad"
}

Access a value:

print(student["name"])

Output:

Sreehari

Average lookup complexity:

O(1)

4.7.6Inserting Values

• Add a new key-value pair:
• student["course"] = "AI/ML"
• Now:

print(student)

might produce:

{

• "name": "Sreehari",
• "age": 37,
• "city": "Hyderabad",
• "course": "AI/ML"

}

Average complexity:

O(1)

4.7.7Updating Values

• If the key already exists:
• student["age"] = 38
• The existing value is replaced.
• Average complexity:

O(1)

4.7.8Deleting Values

• Use del:
• del student["city"]
• Or:
• student.pop("city")
• Average complexity:

O(1)

4.7.9Checking Whether a Key Exists

Use in:

if "name" in student:
print("Name exists")

Average complexity:

O(1)

This is one of the most useful operations in DSA.

4.7.10Dictionary Methods

• Important Python dictionary methods include:
• student.keys()
• student.values()
• student.items()
• student.get("name")
• student.pop("name")
• student.update(...)

Example:

student = {
    "name": "Sreehari",
    "age": 37
}

print(student.keys())
print(student.values())
print(student.items())

4.7.11get() Method

Direct access:

value = student["name"]

raises a KeyError if the key doesn't exist.

Using:

value = student.get("name")

returns the value.

For a missing key:

value = student.get("salary")

returns:

None

You can specify a default:

value = student.get("salary", 0)

Result:

0

4.7.12Dictionary Frequency Counting

One of the most important applications of hash tables is frequency counting.

Suppose:

numbers = [1, 2, 2, 3, 3, 3]

• We want:
• 1 → 1
• 2 → 2
• 3 → 3
• Implementation:

frequency = {}
for number in numbers:
    frequency[number] = frequency.get(number, 0) + 1

print(frequency)

Output:

{1: 1, 2: 2, 3: 3}

Typical complexity:

Time = O(n)

Space = O(k)

where k is the number of distinct values.

4.7.13Character Frequency

The same technique works for strings.

text = "banana"
frequency = {}
for character in text:
    frequency[character] = frequency.get(character, 0) + 1

print(frequency)

Output:

{'b': 1, 'a': 3, 'n': 2}

This pattern is extremely common in coding interviews.

4.7.14Two Sum Problem

One of the most famous hash-table problems is Two Sum.

Given:

numbers = [2, 7, 11, 15]
target = 9

• We want two numbers whose sum is 9.
• The brute-force approach uses nested loops:
• Time = O(n²)

A hash table can improve this to average:

Time = O(n)

Implementation:

def two_sum(numbers, target):
seen = {}
for i, number in enumerate(numbers):
required = target - number
if required in seen:
return [seen[required], i]

seen[number] = i

return []

Example:

print(two_sum([2, 7, 11, 15], 9))

Output:

The hash table allows us to quickly determine whether the required complement has already been seen.

4.7.15How Two Sum Works

Input:

• Target:
• 9
• First value:

number = 2
required = 9 - 2 = 7

• 7 isn't in the hash table.
• Store:
• 2 → index 0
• Next:

number = 7
required = 9 - 7 = 2

2 exists.

Therefore:

2 + 7 = 9

We have solved the problem in one pass.

4.7.16Duplicate Detection

Hash tables are excellent for detecting duplicates.

def has_duplicate(numbers):
seen = set()
for number in numbers:
if number in seen:
return True

seen.add(number)

return False

Complexity:

Time = O(n) average

Space = O(n)

A set is essentially a hash-based collection of unique values.

4.7.17Hash Table vs Set

• A dictionary stores:
• Key → Value
• A set stores:
• Unique Keys
• Example dictionary:

student = {
    "name": "Sreehari",
    "age": 37
}

Example set:

numbers = {10, 20, 30}

Both are hash-based structures in Python.

4.7.18Hash Collisions

• A collision occurs when two different keys map to the same bucket.
• Conceptually:
• Key A ──┐
• ├──→ Bucket 5
• Key B ──┘
• For example:
• hash("apple") → bucket 5
• hash("orange") → bucket 5
• Both keys want the same location.
• A hash-table implementation must handle this situation.

4.7.19Collision Resolution

• Two major collision-resolution techniques are:
• Separate Chaining
• Open Addressing

4.7.20Separate Chaining

• In separate chaining, each bucket can hold multiple entries.
• Conceptually:
• Bucket 0 → ...
• Bucket 1 → ...
• Bucket 2 → Key A → Key B
• Bucket 3 → ...
• Bucket 4 → ...

If two keys map to the same bucket, they can be stored in a chain associated with that bucket.

The chain may be implemented using a linked structure or another suitable representation.

4.7.21Open Addressing

• In open addressing, all entries are stored inside the table itself.
• If the preferred bucket is occupied, another location is searched according to a probing strategy.
• Common techniques include:
• Linear probing
• Quadratic probing
• Double hashing

4.7.22Linear Probing

Suppose the preferred position is occupied.

The algorithm checks the next position:

6 → occupied

• 7 → empty
• The new element is placed at index 7.
• The basic probing sequence is conceptually:
• index
• index + 1
• index + 2
• index + 3

...

with wraparound when necessary.

4.7.23Quadratic Probing

Instead of checking positions linearly, quadratic probing uses increasing offsets such as:

• index + 1²
• index + 2²
• index + 3²

...

This can reduce some clustering patterns compared with simple linear probing.

4.7.24Double Hashing

• Double hashing uses a second hash function to determine the probing step.
• Conceptually:
• index = hash1(key)
• step = hash2(key)
• Then:
• index
• index + step
• index + 2 × step
• index + 3 × step

...

This can provide better distribution than simple linear probing.

4.7.25Load Factor

• The load factor measures how full a hash table is.
• It is commonly represented as:
• α = Number of Stored Elements / Number of Buckets
• For example:

Elements = 7
Buckets  = 10

Then:

α = 7 / 10

= 0.7

A high load factor generally increases collision probability and can reduce performance.

4.7.26Resizing

When a hash table becomes too full, implementations may resize it.

Conceptually:

The elements may need to be placed into new buckets because the table size changed.

This operation can be expensive individually, but resizing strategies allow insertion to remain efficient amortized over a sequence of operations.

4.7.27Average vs Worst-Case Complexity

Typical hash-table complexity is:

• Why can the worst case become O(n)?
• Because many keys could experience collisions, causing the implementation to examine many entries.
• Good hash functions and appropriate table management make average-case performance close to O(1).

4.7.28Hashable Keys in Python

• Dictionary keys must be hashable.
• Common hashable types include:
• int
• float
• str
• bool
• tuple
• For example:

data = {
    "name": "Sreehari",
    100: "value",
    (1, 2): "point"
}

Lists cannot normally be dictionary keys:

data = {
    [1, 2]: "value"
}

because lists are mutable and unhashable.

4.7.29Immutable Objects as Keys

A key should have a stable hash value while it is being used in a dictionary.

For example:

location = {
    (12.9, 77.6): "Bangalore"
}

A tuple can be used as a key when its contents are hashable.

This is useful for representing coordinates or composite keys.

4.7.30Grouping Data

• Hash tables are useful for grouping records.
• Suppose:
• Students:
• Alice → CSE

Bob → ECE

Charlie → CSE

David → ECE

We can group them by department:

groups = {}
students = [
    ("Alice", "CSE"),
    ("Bob", "ECE"),
    ("Charlie", "CSE"),
    ("David", "ECE")
]

for name, department in students:
    groups.setdefault(department, []).append(name)

print(groups)

Result:

{

"CSE": ["Alice", "Charlie"],

"ECE": ["Bob", "David"]

}

This is another important hash-table pattern.

4.7.31Counting with Counter

Python provides collections.Counter for frequency counting.

from collections import Counter
numbers = [1, 2, 2, 3, 3, 3]
counts = Counter(numbers)
print(counts)

Output:

• Counter({3: 3, 2: 2, 1: 1})
• For strings:
• Counter("banana")
• produces frequency information for each character.

4.7.32Hash Tables and Caching

Hash tables are commonly used for caches.

Suppose an expensive function produces a result:

Input → Expensive Calculation → Result

Instead of calculating it repeatedly:

A dictionary can serve as the cache:

cache = {}
def expensive_operation(x):
if x in cache:
return cache[x]
result = x * x

cache[x] = result

return result

Typical lookup:

O(1) average

This idea is fundamental to memoization and dynamic programming.

4.7.33Hash Tables in Dynamic Programming

• Consider Fibonacci.
• Naive recursion repeatedly calculates the same values.
• Memoization stores previously calculated results:

memo = {}
def fibonacci(n):
if n <= 1:
return n
if n in memo:
return memo[n]

memo[n] = fibonacci(n - 1) + fibonacci(n - 2)

return memo[n]

The dictionary provides fast lookup of previously computed values.

This is a major connection between:

4.7.34Hash Tables in Graph Algorithms

• Hash tables and sets are heavily used in graph problems.
• For example:
• visited = set()
• can track which vertices have already been visited.

if neighbor not in visited:
    visited.add(neighbor)

Average membership testing is:

O(1)

This makes hash-based structures extremely useful for BFS and DFS.

4.7.35Hash Table for Word Frequency

Suppose we have:

"python is easy and python is powerful"

We can count words:

from collections import Counter
text = "python is easy and python is powerful"
words = text.split()
frequency = Counter(words)
print(frequency)

Result:

{

"python": 2,

"is": 2,

"easy": 1,

"and": 1,

"powerful": 1

}

• This technique is fundamental in:
• NLP
• Search engines
• Log analysis
• Text analytics
• Machine learning preprocessing

4.7.36Hash Tables in AI and Machine Learning

• Hash-based structures are useful throughout AI/ML systems.
• Examples include:
• Feature Frequency
• word → frequency
• Vocabulary
• token → ID
• For example:
• "machine" → 105
• "learning" → 237
• Caching
• input → model result
• Deduplication
• hash → document
• Lookup Tables
• category → metadata
• NLP
• word → count
• word → token ID

Hash tables therefore provide a foundation for many data-processing operations used in AI systems.

4.7.37Important Hash Table Interview Patterns

1. Frequency Map

• Element → Count
• Used for:
• Character frequency
• Word frequency
• Anagrams
• Majority elements

2. Seen Set

• Element → Already Seen?
• Used for:
• Duplicate detection
• Cycle detection
• Visited tracking

3. Complement Lookup

• Used in:
• Two Sum
• Pair problems

4. Grouping

• Key → List of Values
• Used in:
• Group Anagrams
• Categorization
• Aggregation

5. Memoization

• Input → Computed Result
• Used in:
• Dynamic Programming
• Recursive optimization

4.7.38Group Anagrams

Given:

we want:

[

["eat", "tea", "ate"],

["tan", "nat"],

]

• A hash table can group words using a canonical key.
• For example:
• eat → aet
• tea → aet
• ate → aet
• Implementation:

from collections import defaultdict
def group_anagrams(words):
groups = defaultdict(list)
for word in words:
key = "".join(sorted(word))

groups[key].append(word)

return list(groups.values())

The dictionary maps:

canonical representation → words

This is a classic hash-table interview problem.

4.7.39Longest Consecutive Sequence

Given:

• the longest consecutive sequence is:
• 1, 2, 3, 4
• Length:
• 4
• A set allows fast membership checks.

def longest_consecutive(numbers):
    values = set(numbers)
    longest = 0
    for number in values:
        if number - 1 not in values:
            current = number
            length = 1
            while current + 1 in values:
                current += 1

length += 1

longest = max(longest, length)

return longest

Typical complexity:

Time = O(n) average

Space = O(n)

This is an excellent example of replacing sorting with hashing.

4.7.40Hash Table vs Array

Use an array when position matters.

Use a hash table when fast key-based lookup matters.

4.7.41Hash Table vs Linked List

These structures solve different problems.

4.7.42When Should You Use a Hash Table?

Consider a hash table when you need:

• Fast lookup by key.
• Frequency counting.
• Duplicate detection.
• Membership testing.
• Grouping.
• Caching.
• Mapping one object to another.
• Memoization.
• Tracking visited objects.
• A useful interview question is:
• Can I use a hash table to remember something I've already seen?

If the answer is yes, there may be an O(n) solution hiding behind an O(n²) brute-force solution.

4.7.43Important Hash Table Problems

Beginner

• Count frequencies.
• Check for duplicates.
• Find first non-repeating character.
• Find the most frequent element.
• Check whether two arrays contain the same elements.
• Find common elements.
• Find missing values.

Intermediate

• Two Sum.
• Group Anagrams.
• Longest Consecutive Sequence.
• Subarray Sum Equals K.
• Longest Subarray with Given Sum.
• Isomorphic Strings.
• Word Pattern.
• Happy Number.
• Top K Frequent Elements.
• Find All Duplicates.

Advanced

• LRU Cache.
• Minimum Window Substring.
• Longest Substring Without Repeating Characters.
• Four Sum / Four Sum Count.
• Design a Hash Map.
• Design a Hash Set.
• Randomized Set.
• Time-Based Key-Value Store.

4.7.44Designing a Simple Hash Table

A simplified hash table can be implemented from scratch.

class HashTable:
    def __init__(self, capacity=10):
        self.capacity = capacity

self.table = [[] for _ in range(capacity)]

def _index(self, key):
    return hash(key) % self.capacity
    def put(self, key, value):
        index = self._index(key)
        for i, (existing_key, _) in enumerate(self.table[index]):
            if existing_key == key:
                self.table[index][i] = (key, value)

return

self.table[index].append((key, value))

def get(self, key):
index = self._index(key)
for existing_key, value in self.table[index]:
if existing_key == key:
return value
return None

This simplified implementation uses separate chaining.

The real Python dict implementation is significantly more sophisticated and optimized.

4.7.45Complexity of the Simple Implementation

Average case:

put() → O(1)

get() → O(1)

Worst case:

put() → O(n)

get() → O(n)

The worst case occurs when many keys collide into the same bucket.

4.7.46Hash Table Security Considerations

• Hash tables can also have security implications.
• If an attacker can deliberately create large numbers of colliding keys, operations may become much slower.
• Production-quality implementations therefore use carefully designed hashing strategies and table-management techniques.

Python's hashing behavior also has security-related implementation details, including randomized hashing for certain built-in types such as strings.

4.7.47Complexity Summary

Space complexity:

O(n)

for storing n key-value entries.

4.7.48Key Takeaways

• The central idea is:
• A hash table maps keys to values so that key-based lookup can be performed in O(1) average time.
• Remember:

• Important concepts:
• Hash Function
• Hashing
• Collision
• Separate Chaining
• Open Addressing
• Linear Probing
• Quadratic Probing
• Double Hashing
• Load Factor
• Resizing

For Python, the most important structures are:

dict

set

And the most important interview patterns are:

• Frequency Map
• Seen Set
• Two Sum / Complement Lookup
• Grouping
• Memoization
• Caching

The most important complexity to remember is:

• Hash Table Lookup → O(1) average
• Hash Table Insert → O(1) average
• Hash Table Delete → O(1) average

Once you understand hash tables, many apparently expensive O(n²) problems can often be transformed into efficient O(n) solutions by using additional memory.

• A Tree is a non-linear hierarchical data structure consisting of nodes connected by edges.
• Unlike arrays, linked lists, stacks, and queues—which are generally linear—trees represent relationships in a hierarchy.
• Examples of hierarchical structures include:
• File systems
• Organization charts
• HTML/XML documents
• Database indexes
• Decision trees
• Compiler syntax trees
• AI search structures
• A simple tree looks like:
• 10

/ \

5 20

/ \ / \

3 7 15 25

Here, 10 is at the top and the other nodes branch underneath it.

4.8.1Basic Terminology

• Understanding tree terminology is essential before learning binary trees, binary search trees, heaps, and tries.
• Consider:
• A

/ \

B C

/ \ \

D E F

• Root
• The topmost node is called the root.
• Root = A

A tree normally has exactly one root.

• Parent
• A node directly above another node is its parent.
• A → B
• A is the parent of B.
• Child

A node directly below another node is its child.

B is a child of A.

• Siblings
• Nodes with the same parent are called siblings.
• A

/ \

B C

B and C are siblings.

4.8.2Leaf Node

• A leaf node is a node that has no children.
• In:
• A

/ \

B C

/ \ \

D E F

• the leaf nodes are:
• D
• E
• F

Leaf nodes are also called terminal nodes.

4.8.3Internal Node

• A node with at least one child is generally called an internal node or non-leaf node.
• In the example:
• A
• B
• C
• are internal nodes.

4.8.4Edge

An edge connects two nodes.

A

|

• B
• The connection between A and B is an edge.
• A tree containing n nodes has:
• n - 1
• edges.
• For example:
• 5 nodes → 4 edges

4.8.5Path

• A path is a sequence of nodes connected by edges.
• For example:
• A → B → E
• is a path.

The number of edges in the path is its path length.

4.8.6Depth of a Node

• The depth of a node is the number of edges from the root to that node.
• Consider:
• A

/ \

B C

/ \

D E

• Depth:
• A → 0
• B → 1
• C → 1
• D → 2
• E → 2
• The root has depth 0.

4.8.7Height of a Node

The height of a node is the number of edges on the longest downward path from that node to a leaf.

For:

A

/

B

/

• C
• we have:
• height(C) = 0
• height(B) = 1
• height(A) = 2

The height of a tree is the height of its root.

4.8.8Level

Nodes at the same depth are commonly considered to be at the same level.

Example:

A Level 0

/ \

B C Level 1

/ \ / \

D E F G Level 2

This concept is particularly important for level-order traversal.

4.8.9Subtree

• A subtree is a tree formed by a node and all of its descendants.
• Consider:
• A

/ \

B C

/ \

D E

The subtree rooted at B is:

B

/ \

D E

4.8.10Ancestor and Descendant

For:

A

/

B

/

• C
• A is an ancestor of:
• B
• C
• C is a descendant of:
• A
• B

These relationships are important in many tree algorithms.

4.8.11Degree of a Node

The degree of a node is the number of children it has.

Example:

A

/ | \

B C D

• Here:
• degree(A) = 3
• degree(B) = 0
• degree(C) = 0
• degree(D) = 0

In a binary tree, the maximum degree of a node is 2.

4.8.12General Tree

A general tree is a tree in which a node can have any number of children.

Example:

A

/ | \

B C D

/ | \ / \

E F G H I

• A has three children.
• B has three children.
• D has two children.

There is no fixed maximum number of children.

4.8.13Binary Tree

• A binary tree is a tree in which each node has at most two children.
• The children are called:
• Left Child
• Right Child

Example:

10

/ \

5 20

/ \

3 7

• A node can have:
• 0 children
• 1 child
• 2 children
• but never more than two.

Binary trees are covered in detail in Section 4.9.

4.8.14Tree Representation

A basic tree node can be represented using a Python class.

For a binary-tree-style node:

class TreeNode:
    def __init__(self, value):
        self.value = value

• self.left = None
• self.right = None
• Create nodes:
• root = TreeNode(10)
• root.left = TreeNode(5)
• root.right = TreeNode(20)
• This creates:
• 10

/ \

5 20

4.8.15General Tree Representation

For a general tree, a node may contain a list of children.

class TreeNode:
    def __init__(self, value):
        self.value = value

• self.children = []
• Then:
• root = TreeNode("A")
• root.children.append(TreeNode("B"))
• root.children.append(TreeNode("C"))
• root.children.append(TreeNode("D"))
• Structure:
• A

/ | \

B C D

4.8.16Tree Traversal

• Tree traversal means visiting all nodes of a tree according to a particular strategy.
• The major traversal techniques are:
• Preorder
• Inorder
• Postorder
• Level Order

For a general tree, preorder and level-order are particularly common.

For binary trees, all four are important.

4.8.17Preorder Traversal

In preorder:

For a binary tree:

Node → Left → Right

Example:

A

/ \

B C

/ \

D E

Preorder:

A B D E C

4.8.18Preorder Algorithm

def preorder(root):
    if root is None:
        return

print(root.value)

• preorder(root.left)
• preorder(root.right)
• For:
• A

/ \

B C

/ \

D E

• the traversal is:
• A → B → D → E → C
• Time complexity:

O(n)

because every node is visited once.

4.8.19Inorder Traversal

Inorder is primarily defined for binary trees:

For:

A

/ \

B C

/ \

D E

the inorder traversal is:

D B E A C

Inorder traversal becomes especially important for Binary Search Trees because it visits values in sorted order.

4.8.20Postorder Traversal

Postorder:

For:

A

/ \

B C

/ \

D E

postorder is:

• D E B C A
• Postorder is useful when child nodes must be processed before their parent.
• Examples:
• Deleting a tree
• Evaluating expression trees
• Calculating subtree properties

4.8.21Level-Order Traversal

Level-order traversal visits nodes level by level.

Example:

A

/ \

B C

/ \ \

D E F

Level order:

A B C D E F

It is typically implemented using a queue.

4.8.22Level-Order Implementation

from collections import deque
def level_order(root):
if root is None:
return []
result = []
queue = deque([root])
while queue:
node = queue.popleft()

result.append(node.value)

if node.left:
    queue.append(node.left)

if node.right:
    queue.append(node.right)

return result

Complexity:

Time = O(n)

Space = O(n)

This demonstrates the relationship:

4.8.23Recursive Tree Traversal

Trees naturally support recursive algorithms.

For example:

def preorder(root):
    if root is None:
        return

print(root.value)

• preorder(root.left)
• preorder(root.right)
• Why does recursion work well?
• Because every subtree is itself a smaller tree.
• Tree
• ├── Left Subtree
• └── Right Subtree

This recursive structure is fundamental to tree algorithms.

4.8.24Tree Height

We can calculate tree height recursively.

def height(root):
    if root is None:
        return -1
        return 1 + max(
            height(root.left),
            height(root.right)
        )

For:

A

/

B

/

• C
• the height is:
• 2

because the longest path has two edges.

4.8.25Counting Nodes

def count_nodes(root):
    if root is None:
        return 0
        return (
            1
            + count_nodes(root.left)
            + count_nodes(root.right)
        )

For:

A

/ \

B C

• result:
• 3
• Complexity:

Time = O(n)

Space = O(h)

where h is the tree height due to recursion.

4.8.26Counting Leaf Nodes

def count_leaves(root):
    if root is None:
        return 0
        if root.left is None and root.right is None:
            return 1
            return (
                count_leaves(root.left)
                + count_leaves(root.right)
            )

This visits every node:

Time = O(n)

4.8.27Maximum Value in a Tree

For a general binary tree without ordering guarantees:

def maximum_value(root):
if root is None:
return float("-inf")
left_max = maximum_value(root.left)
right_max = maximum_value(root.right)
return max(root.value, left_max, right_max)

Because every node may need to be examined:

Time = O(n)

This differs from a Binary Search Tree, where ordering can sometimes eliminate entire subtrees.

4.8.28Balanced Tree

A tree is considered balanced when its subtrees have reasonably similar heights.

For a binary tree, a common definition is:

• For every node:
• |height(left) - height(right)| ≤ 1
• Example of a balanced structure:
• 10

/ \

5 20

/ \ / \

2 7 15 25

A highly unbalanced tree can look like:

10

\

20

\

30

\

40

The second structure behaves much like a linked list.

4.8.29Why Tree Balance Matters

• Consider searching in a tree.
• A balanced tree:
• 8

/ \

4 12

/ \ / \

2 6 10 14

• has height approximately:
• O(log n)
• An unbalanced tree:
• 2

\

4

\

6

\

8

has height:

O(n)

This is why balanced search trees are important.

• Examples include:
• AVL Trees
• Red-Black Trees

4.8.30Full Binary Tree

A full binary tree is a binary tree in which every node has either:

• 0 children
• or:
• 2 children

Example:

1

/ \

2 3

/ \

4 5

There are no nodes with exactly one child.

4.8.31Complete Binary Tree

• A complete binary tree has:
• Every level completely filled except possibly the last.
• The last level is filled from left to right.

Example:

1

/ \

2 3

/ \ /

4 5 6

This concept is particularly important for heaps.

4.8.32Perfect Binary Tree

• A perfect binary tree has:
• Every internal node with exactly two children.
• All leaves at the same level.

Example:

1

/ \

2 3

/ \ / \

4 5 6 7

If the tree has height h, a perfect binary tree contains:

2^(h+1) - 1

nodes when the root is at height 0.

4.8.33Degenerate Tree

A degenerate tree is essentially a tree where each node has only one child.

Example:

10

\

20

\

30

\

• 40
• This behaves similarly to a linked list.
• Height:

O(n)

4.8.34Tree Representation Using Arrays

Some trees can be represented efficiently using arrays.

For a complete binary tree, nodes can be stored level by level:

10

/ \

20 30

/ \

40 50

Array:

With zero-based indexing:

left child = 2*i + 1

right child = 2*i + 2

parent = (i - 1) // 2

This representation is especially important for heaps.

4.8.35Tree Representation Using References

For a binary tree:

class TreeNode:
    def __init__(self, value):
        self.value = value

self.left = None

self.right = None

This representation is flexible and works well for arbitrary binary trees.

4.8.36Tree Traversal Complexity

For a tree with n nodes:

• Where:
• h = tree height
• w = maximum width of the tree
• For a balanced tree:
• h = O(log n)
• For a skewed tree:

h = O(n)

4.8.37Tree Search

For a general tree, there is no ordering guarantee.

Therefore, searching may require visiting every node.

Using DFS:

def search(root, target):
    if root is None:
        return False
        if root.value == target:
            return True
            return (
                search(root.left, target)
                or search(root.right, target)
            )

Worst-case complexity:

O(n)

A Binary Search Tree can improve this significantly when balanced.

4.8.38Lowest Common Ancestor

The Lowest Common Ancestor (LCA) of two nodes is the lowest node in the tree that is an ancestor of both.

Example:

A

/ \

B C

/ \ / \

D E F G

• The LCA of:
• D and E
• is:
• B
• The LCA of:
• D and G
• is:
• A

LCA problems are extremely common in coding interviews.

4.8.39Diameter of a Tree

The diameter of a tree is the longest path between two nodes.

Example:

1

/ \

2 3

/ \

4 5

• One longest path is:
• 4 → 2 → 1 → 3
• The diameter is:
• 3 edges

A good solution can calculate the diameter in:

O(n)

using a postorder-style height calculation.

4.8.40Tree Applications

• Trees are used extensively in computing.
• File Systems
• Computer
• ├── Documents
• ├── Pictures
• └── Videos
• Organization Hierarchies
• CEO
• ├── Manager A

│ ├── Employee 1

│ └── Employee 2

• └── Manager B
• HTML DOM
• html
• ├── head
• └── body

├── div

└── p

• Database Indexes
• Trees are used extensively for efficient indexing.
• AI Decision Trees
• Is age > 30?

/ \

Yes No

/ \

Approved Review

Compilers

Source code can be represented as syntax trees.

4.8.41Trees in AI and Machine Learning

Trees are particularly important in AI/ML.

Decision Trees

A decision tree repeatedly splits data based on features.

Example:

Income > 50K?

/ \

Yes No

/ \

Credit > 700? Reject

/ \

Yes No

/ \

Approve Review

• Random Forest
• A Random Forest combines multiple decision trees.
• Dataset

↓

┌──────┼──────┐

↓ ↓ ↓

Tree 1 Tree 2 Tree 3

↓ ↓ ↓

└──────┼──────┘

↓

Prediction

• Gradient Boosting
• Algorithms such as gradient-boosted trees build trees sequentially to improve predictions.
• Trees therefore form an important bridge between DSA and Machine Learning.

4.8.42Tree vs Graph

• Trees are actually a special type of graph.
• A tree generally has:
• Connected structure
• No cycles
• n - 1 edges for n nodes
• A general graph may have:
• Cycles
• Multiple paths
• Disconnected components
• Arbitrary edge counts
• Example tree:
• A

├── B

└── C

Example graph:

A ─── B

│ / │

│ / │

C ─── D

The graph can contain cycles, while a tree cannot.

4.8.43Important Tree Properties

For a tree with n nodes:

• Edges = n - 1
• There is exactly one simple path between any two nodes.
• A tree is connected.
• A tree contains no cycles.
• Removing any edge disconnects the tree.
• Adding an edge to a tree creates a cycle.
• These properties are fundamental to graph theory.

4.8.44Important Tree Interview Patterns

1. DFS

Use recursion or an explicit stack.

2. BFS

Use a queue.

3. Divide and Conquer

Solve:

Left subtree

+

Right subtree

+

Current node

4. Bottom-Up Recursion

• Calculate information from children before processing the parent.
• Used for:
• Height
• Diameter
• Balance
• Maximum path sum

5. Top-Down Recursion

• Pass information from the parent toward children.
• Used for:
• Path constraints
• Root-to-leaf problems
• Depth calculations

4.8.45Common Tree Problems

Beginner

• Create a tree.
• Count nodes.
• Find tree height.
• Count leaf nodes.
• Search for a value.
• Preorder traversal.
• Inorder traversal.
• Postorder traversal.
• Level-order traversal.
• Find maximum value.

Intermediate

• Check if two trees are identical.
• Check if a tree is balanced.
• Find tree diameter.
• Find lowest common ancestor.
• Invert a binary tree.
• Find maximum depth.
• Find minimum depth.
• Root-to-leaf path sum.
• Sum of all nodes.
• Zigzag level-order traversal.

Advanced

• Maximum path sum.
• Serialize and deserialize a tree.
• Construct tree from preorder and inorder.
• Construct tree from inorder and postorder.
• Boundary traversal.
• Vertical order traversal.
• Morris traversal.
• Recover a corrupted search tree.

Flatten a tree into a linked list.

Find nodes at distance K.

4.8.46Tree Complexity Summary

For a generic tree, there is no universal O(log n) search guarantee.

That guarantee appears in specific ordered and balanced tree structures.

4.8.47Important Tree Types to Learn

As you continue through this module, several specialized trees become important:

Your syllabus specifically covers:

4.24Trie

4.25Segment Tree

Each solves a different class of problems.

4.8.48Tree vs Linked List

• A linked list is essentially a restricted tree-like structure where nodes normally have at most one next direction.
• Linked List:
• 10 → 20 → 30 → 40
• A tree branches:
• 10

/ \

20 30

/ \ \

40 50 60

The major advantage of trees is that they can represent hierarchical relationships and, in specialized forms, support efficient searching.

4.8.49Key Takeaways

• The most important tree terminology is:
• Root
• Parent
• Child
• Sibling
• Leaf
• Internal Node
• Edge
• Path
• Depth
• Height
• Subtree
• Ancestor
• Descendant
• Degree
• The major traversal methods are:

Preorder → Node → Left → Right

Inorder → Left → Node → Right

Postorder → Left → Right → Node

• Level Order → Level by Level
• The most important structural types are:
• General Tree
• Binary Tree
• Full Binary Tree
• Complete Binary Tree
• Perfect Binary Tree
• Balanced Tree
• Degenerate Tree
• And remember these fundamental properties:

Finally, the most important algorithms and patterns to master are:

DFS, BFS, recursion, tree height, tree diameter, lowest common ancestor, subtree processing, and top-down/bottom-up recursion.

The next section, 4.9 Binary Trees, builds directly on these concepts and introduces the two-child left/right structure that forms the foundation for BSTs, heaps, expression trees, and many tree interview problems.

4.9Binary Trees

4.9Binary Trees

• A Binary Tree is a tree data structure in which each node has at most two children.
• The two children are called:
• Left child
• Right child
• A binary tree can look like:
• 10

/ \

5 20

/ \ \

3 7 30

• Each node can have:
• 0 children
• 1 child
• 2 children
• but never more than two.

4.9.1Binary Tree Node

A binary-tree node normally contains three components:

• Node
• ├── Data
• ├── Left
• └── Right
• In Python:

class TreeNode:
    def __init__(self, value):
        self.value = value

• self.left = None
• self.right = None
• Create a simple binary tree:
• root = TreeNode(10)
• root.left = TreeNode(5)
• root.right = TreeNode(20)
• The structure is:
• 10

/ \

5 20

4.9.2Building a Binary Tree

Let's create a larger tree:

• root = TreeNode(10)
• root.left = TreeNode(5)
• root.right = TreeNode(20)
• root.left.left = TreeNode(3)
• root.left.right = TreeNode(7)
• root.right.right = TreeNode(30)
• The resulting tree:
• 10

/ \

5 20

/ \ \

3 7 30

Notice that the tree does not necessarily have to be sorted.

That distinction becomes important when we study Binary Search Trees.

4.9.3Binary Tree Terminology

Consider:

A

/ \

B C

/ \ \

D E F

• Root
• A
• is the root.
• Children

B and C are children of A.

• Parent
• A is the parent of B and C.
• Siblings
• B and C are siblings.
• D and E are siblings.
• Leaf Nodes
• D, E, F
• are leaf nodes.
• Internal Nodes
• A, B, C
• are internal nodes.

4.9.4Binary Tree Properties

For a binary tree:

Each node can have at most two children.

Therefore, at level 0:

• Maximum nodes = 1
• At level 1:
• Maximum nodes = 2
• At level 2:
• Maximum nodes = 4
• At level 3:
• Maximum nodes = 8

In general, the maximum number of nodes at level L is:

2^L

when the root is at level 0.

4.9.5Maximum Number of Nodes

For a binary tree of height h, where the root has height 0, the maximum number of nodes is:

2^(h + 1) - 1

For example, height 2:

A

/ \

B C

/ \ / \

D E F G

Number of nodes:

2^(2 + 1) - 1

= 8 - 1

= 7

4.9.6Minimum Height

• A binary tree containing n nodes can have a minimum height when it is as balanced as possible.
• Approximately:
• h = O(log n)

This is why balanced binary trees can support efficient operations.

4.9.7Maximum Height

The maximum height occurs when every node has only one child.

Example:

10

\

20

\

30

\

40

\

• 50
• If there are n nodes:
• height = n - 1

Therefore:

Minimum height → O(log n)

Maximum height → O(n)

4.9.8Full Binary Tree

A Full Binary Tree is a binary tree where every node has either:

• 0 children
• or:
• 2 children

Example:

1

/ \

2 3

/ \

4 5

• Node 2 has two children.
• Node 3 has zero children.
• Node 4 and 5 have zero children.
• There are no nodes with exactly one child.

4.9.9Complete Binary Tree

• A Complete Binary Tree has:
• Every level completely filled except possibly the last.
• The last level filled from left to right.

Example:

1

/ \

2 3

/ \ /

4 5 6

This is complete.

But:

1

/ \

2 3

/ \

4 6

is not complete because the last level is not filled from left to right.

Complete binary trees are especially important for heaps.

4.9.10Perfect Binary Tree

• A Perfect Binary Tree has:
• Every internal node with exactly two children.
• All leaf nodes at the same level.

Example:

1

/ \

2 3

/ \ / \

4 5 6 7

For height h:

Nodes = 2^(h + 1) - 1

4.9.11Balanced Binary Tree

A balanced binary tree has subtrees whose heights remain reasonably close.

Example:

10

/ \

5 20

/ \ / \

3 7 15 25

• A balanced tree generally has:
• Height = O(log n)
• Balanced trees are important for efficient searching.

4.9.12Degenerate Binary Tree

A degenerate binary tree has essentially one child at each level.

Example:

10

\

20

\

30

\

• 40
• It behaves almost like a linked list.
• For n nodes:
• Height = O(n)

4.9.13Skewed Binary Tree

• A skewed tree can lean entirely to one side.
• Left-skewed
• 40

/

30

/

20

/

• 10
• Right-skewed
• 10

\

20

\

30

\

40

Both have height:

O(n)

4.9.14Binary Tree Traversals

The four major traversal techniques are:

• 1. Preorder
• 2. Inorder
• 3. Postorder
• 4. Level Order

Consider:

1

/ \

2 3

/ \

4 5

4.9.15Preorder Traversal

Preorder follows:

For:

1

/ \

2 3

/ \

4 5

• the result is:
• 1 2 4 5 3
• Implementation:

def preorder(root):
    if root is None:
        return

print(root.value)

• preorder(root.left)
• preorder(root.right)
• Complexity:

Time = O(n)

Space = O(h)

where h is the tree height.

4.9.16Inorder Traversal

Inorder follows:

For:

1

/ \

2 3

/ \

4 5

• the result is:
• 4 2 5 1 3
• Implementation:

def inorder(root):
    if root is None:
        return

inorder(root.left)

print(root.value)

inorder(root.right)

Inorder traversal becomes especially important for Binary Search Trees, where it produces values in sorted order.

4.9.17Postorder Traversal

Postorder follows:

For:

1

/ \

2 3

/ \

4 5

• the result is:
• 4 5 2 3 1
• Implementation:

def postorder(root):
    if root is None:
        return

postorder(root.left)

postorder(root.right)

print(root.value)

Postorder is useful when children must be processed before their parent.

4.9.18Level-Order Traversal

Level-order visits nodes level by level.

Example:

1

/ \

2 3

/ \

4 5

• Result:
• 1 2 3 4 5
• Implementation:

from collections import deque
def level_order(root):
if root is None:
return []
result = []
queue = deque([root])
while queue:
node = queue.popleft()

result.append(node.value)

if node.left:
    queue.append(node.left)

if node.right:
    queue.append(node.right)

return result

Complexity:

Time = O(n)

Space = O(w)

where w is the maximum width of the tree.

4.9.19Traversal Summary

For:

1

/ \

2 3

/ \

4 5

• A useful memory trick:
• PRE:
• Node first
• IN:
• Node in the middle
• POST:
• Node last

4.9.20Iterative Preorder

Preorder can be implemented without recursion using a stack.

def preorder_iterative(root):
if root is None:
return []
result = []
stack = [root]
while stack:
node = stack.pop()

result.append(node.value)

if node.right:
    stack.append(node.right)

if node.left:
    stack.append(node.left)

return result

• Why add the right child first?
• Because the stack is LIFO.
• We want the left child to be processed first.

4.9.21Iterative Inorder

Inorder can also be implemented using a stack.

def inorder_iterative(root):
    result = []
    stack = []
    current = root
    while current is not None or stack:
        while current is not None:
            stack.append(current)

current = current.left
current = stack.pop()

result.append(current.value)

current = current.right
return result

This is a very important interview pattern.

4.9.22Iterative Postorder

Postorder can be implemented using stacks as well.

A simple two-stack approach:

def postorder_iterative(root):
if root is None:
return []
stack1 = [root]
stack2 = []
result = []
while stack1:
node = stack1.pop()

stack2.append(node)

if node.left:
    stack1.append(node.left)

if node.right:
    stack1.append(node.right)

while stack2:
    result.append(stack2.pop().value)

return result

There are also optimized one-stack approaches.

4.9.23Finding Maximum Depth

The maximum depth is the longest distance from the root to a leaf.

def max_depth(root):
if root is None:
return 0
left_depth = max_depth(root.left)
right_depth = max_depth(root.right)
return 1 + max(left_depth, right_depth)

Complexity:

Time = O(n)

• Space = O(h)
• For a balanced tree:
• h = O(log n)
• For a skewed tree:

h = O(n)

4.9.24Minimum Depth

Minimum depth is the shortest path from the root to a leaf.

def min_depth(root):
    if root is None:
        return 0
        if root.left is None:
            return 1 + min_depth(root.right)
            if root.right is None:
                return 1 + min_depth(root.left)
                return 1 + min(
                    min_depth(root.left),
                    min_depth(root.right)
                )

For shortest-depth problems, BFS can often be especially natural because it processes nodes level by level.

4.9.25Count Nodes

def count_nodes(root):
    if root is None:
        return 0
        return (
            1
            + count_nodes(root.left)
            + count_nodes(root.right)
        )

• Complexity:
• Time = O(n)
• Every node is visited.

4.9.26Sum of Nodes

def sum_tree(root):
    if root is None:
        return 0
        return (
            root.value
            + sum_tree(root.left)
            + sum_tree(root.right)
        )

For:

10

/ \

5 20

• result:
• 35
• Complexity:

O(n)

4.9.27Find Maximum Value

def maximum(root):
    if root is None:
        return float("-inf")
        return max(
            root.value,
            maximum(root.left),
            maximum(root.right)
        )

For a normal binary tree, every node may need to be examined.

Therefore:

Time = O(n)

Do not confuse this with a Binary Search Tree, where ordering provides additional information.

4.9.28Search in a Binary Tree

Because a normal binary tree has no ordering rule, we may need to search the entire tree.

def search(root, target):
    if root is None:
        return False
        if root.value == target:
            return True
            return (
                search(root.left, target)
                or search(root.right, target)
            )

Worst case:

O(n)

4.9.29Invert a Binary Tree

• A famous interview problem is to invert or mirror a binary tree.
• Original:
• 1

/ \

2 3

/ \

4 5

After inversion:

1

/ \

3 2

/ \

5 4

Implementation:

def invert_tree(root):
if root is None:
return None

• root.left, root.right = root.right, root.left
• invert_tree(root.left)
• invert_tree(root.right)

return root

Complexity:

Time = O(n)

Space = O(h)

This is a classic example of recursive tree processing.

4.9.30Check if Two Trees Are Identical

• Given two trees:
• Tree A:
• 1

/ \

2 3

• and:
• Tree B:
• 1

/ \

2 3

• they are identical if:
• Their corresponding values match.
• Their left subtrees match.
• Their right subtrees match.

def same_tree(a, b):
    if a is None and b is None:
        return True
        if a is None or b is None:
            return False
            return (
                a.value == b.value
                and same_tree(a.left, b.left)
                and same_tree(a.right, b.right)
            )

Complexity:

Time = O(n)

4.9.31Check if a Tree Is Symmetric

A tree is symmetric if its left and right sides are mirror images.

Example:

1

/ \

2 2

/ \ / \

3 4 4 3

This is symmetric.

A recursive solution compares:

left.left ↔ right.right

left.right ↔ right.left

def is_mirror(left, right):
    if left is None and right is None:
        return True
        if left is None or right is None:
            return False
            return (
                left.value == right.value
                and is_mirror(left.left, right.right)
                and is_mirror(left.right, right.left)
            )

4.9.32Root-to-Leaf Path

A common problem asks whether there is a path from root to a leaf whose values sum to a target.

Example:

5

/ \

4 8

/ / \

11 7 4

/ \

2 1

• For target:
• 22
• one valid path is:
• 5 → 4 → 11 → 2
• because:
• 5 + 4 + 11 + 2 = 22
• Implementation:

def has_path_sum(root, target):
    if root is None:
        return False
        if root.left is None and root.right is None:
            return root.value == target
            remaining = target - root.value
            return (
                has_path_sum(root.left, remaining)
                or has_path_sum(root.right, remaining)
            )

• Complexity:
• Time = O(n)
• Space = O(h)

4.9.33Lowest Common Ancestor

Consider:

1

/ \

2 3

/ \

4 5

The LCA of 4 and 5 is:

2

For a general binary tree, a recursive approach is:

def lowest_common_ancestor(root, p, q):
if root is None:
return None
if root == p or root == q:
return root
left = lowest_common_ancestor(root.left, p, q)
right = lowest_common_ancestor(root.right, p, q)
if left and right:
return root
return left if left else right

• Complexity:
• Time = O(n)
• Space = O(h)

4.9.34Tree Diameter

• The diameter is the longest path between two nodes.
• Consider:
• 1

/ \

2 3

/ \

4 5

• Longest path:
• 4 → 2 → 1 → 3
• Diameter:
• 3 edges

A common O(n) solution calculates subtree heights.

def diameter(root):
    maximum = 0
    def height(node):
        nonlocal maximum

if node is None:
return 0
left = height(node.left)
right = height(node.right)
maximum = max(maximum, left + right)
return 1 + max(left, right)

height(root)

return maximum

Time complexity:

O(n)

4.9.35Balanced Tree Check

We can check whether a binary tree is height-balanced.

A naive approach repeatedly calculates heights and may become O(n²).

A better bottom-up approach calculates height and balance information together.

def is_balanced(root):
def check(node):
if node is None:
return 0
left = check(node.left)
if left == -1:
return -1
right = check(node.right)
if right == -1:
return -1
if abs(left - right) > 1:
return -1
return 1 + max(left, right)
return check(root) != -1

Complexity:

Time = O(n)

Space = O(h)

This is an excellent example of bottom-up tree recursion.

4.9.36Zigzag Level-Order Traversal

• Normal level order:
• 1
• 2 3
• 4 5 6 7
• Zigzag traversal:
• 1
• 3 2
• 4 5 6 7
• The direction alternates at every level.
• A deque can be useful for this problem.
• This combines:
• Tree

+

BFS

+

Deque

4.9.37Left View of a Binary Tree

The left view contains the first visible node from each level.

Example:

1

/ \

2 3

/ \ \

4 5 6

Left view:

1 2 4

A BFS traversal can track the first node at each level.

4.9.38Right View of a Binary Tree

• The right view contains the last visible node from each level.
• For:
• 1

/ \

2 3

/ \ \

4 5 6

right view:

1 3 6

These problems are common in interviews and demonstrate level-order traversal.

4.9.39Boundary Traversal

Boundary traversal visits the outer boundary of a binary tree.

Conceptually:

Leaf nodes are generally included carefully to avoid duplicates.

This is an advanced traversal problem.

4.9.40Serialize and Deserialize

Serialization converts a tree into a storable/transmittable representation.

Example:

1

/ \

2 3

• could be represented as:
• "1,2,None,None,3,None,None"
• Deserialization reconstructs the tree.
• This problem is important in:
• Data storage
• APIs
• Distributed systems
• Coding interviews

4.9.41Binary Tree and Stack

DFS traversal can be implemented using a stack.

For preorder:

stack = [root]
while stack:
    node = stack.pop()
    if node.right:
        stack.append(node.right)

if node.left:
    stack.append(node.left)

• This demonstrates the connection between:
• Section 4.5 – Stacks
• and:
• Section 4.9 – Binary Trees

4.9.42Binary Tree and Queue

Level-order traversal uses a queue.

• This connects:
• Section 4.6 – Queues
• with binary trees.

This relationship becomes extremely important in coding interviews.

4.9.43Binary Tree vs Binary Search Tree

These are not the same thing.

A Binary Tree only requires:

At most 2 children

There is no requirement that values be ordered.

Example:

10

/ \

50 2

This is a valid binary tree.

• But it is not a valid Binary Search Tree.
• A BST additionally requires an ordering rule.
• Typically:
• Left subtree < Node < Right subtree
• BSTs are covered in the next section.

4.9.44Binary Tree vs Heap

• A heap is also a specialized binary tree.
• A typical binary heap must satisfy:
• Complete binary tree structure.
• Heap-order property.
• For a min-heap:
• Parent ≤ Children

Example:

1

/ \

3 5

/ \

7 9

Heaps are covered in Section 4.11.

4.9.45Binary Trees in AI

Binary trees have several AI and ML applications.

Decision Trees

A decision can branch into two outcomes:

Age > 30?

/ \

Yes No

/ \

Approve Review

• Game Trees
• Game-playing AI can represent possible moves:
• Current State

/ \

Move A Move B

/ \ / \

State State State State

• Algorithms such as Minimax use tree structures.
• Search Problems
• Trees can represent possible states and decisions.

4.9.46Binary Tree Complexity

For a binary tree containing n nodes:

Auxiliary recursion space:

O(h)

where h is tree height.

Therefore:

Balanced tree → O(log n)

Skewed tree → O(n)

4.9.47Important Binary Tree Patterns

Pattern 1 — DFS Recursion

• Used for:
• Traversals
• Height
• Path sums
• Diameter
• Pattern 2 — BFS

• Used for:
• Level order
• Minimum depth
• Tree views
• Zigzag traversal
• Pattern 3 — Bottom-Up
• Left Result

+

• Used for:
• Height
• Diameter
• Balance
• Maximum path sum
• Pattern 4 — Top-Down

• Used for:
• Path problems
• Depth
• Root-to-leaf constraints

4.9.48Common Binary Tree Interview Problems

Beginner

• Preorder traversal
• Inorder traversal
• Postorder traversal
• Level-order traversal
• Maximum depth
• Minimum depth
• Count nodes
• Count leaves
• Search for a value
• Sum of nodes

Intermediate

• Invert binary tree
• Check identical trees
• Check symmetric tree
• Check balanced tree
• Diameter of binary tree
• Lowest Common Ancestor
• Path Sum
• Left View
• Right View
• Zigzag traversal

Advanced

• Maximum path sum
• Serialize and deserialize
• Construct tree from traversals
• Boundary traversal
• Vertical traversal
• Top view
• Bottom view
• Flatten binary tree
• Nodes at distance K
• Morris traversal

4.9.49Quick Revision

Remember the basic structure:

Node

/ \

Left Right

• Each node has at most two children.
• The four major traversals:
• Preorder:
• Node → Left → Right
• Inorder:
• Left → Node → Right
• Postorder:
• Left → Right → Node
• Level Order:
• Level by Level
• For a tree with n nodes:
• Traversal → O(n)

Search → O(n)

Height → O(n)

Recursion uses:

O(h)

• auxiliary space.
• The key structural types are:
• Binary Tree

↓

┌───┼─────────────┐

↓ ↓ ↓

Full Complete Perfect

And the most important distinction is:

A Binary Tree only restricts each node to at most two children. A Binary Search Tree additionally imposes an ordering relationship between left and right subtrees.

That distinction leads directly into 4.10 Binary Search Trees, where the tree structure is combined with an ordering property to support much faster searching in balanced cases.

4.10Binary Search Trees

4.10Binary Search Trees

A Binary Search Tree (BST) is a specialized binary tree that maintains an ordering relationship between the values in its left and right subtrees.

For every node:

Left Subtree < Node < Right Subtree

Example:

50

/ \

30 70

/ \ / \

20 40 60 80

Here:

• All values in the left subtree of 50 are smaller than 50.
• All values in the right subtree of 50 are greater than 50.
• The same rule applies recursively to every node.

This ordering makes searching much more efficient than searching an ordinary binary tree when the BST is reasonably balanced.

4.10.1Binary Tree vs Binary Search Tree

• A Binary Tree only requires:
• Each node has at most 2 children
• It does not require any ordering.

Example:

50

/ \

80 20

This is a valid binary tree.

But it is not a valid BST because:

80 > 50

while 80 is in the left subtree.

A BST requires:

50

/ \

< 50 > 50

4.10.2BST Property

Consider:

50

/ \

30 70

/ \ / \

20 40 60 80

For node 50:

Left subtree → 20, 30, 40

Right subtree → 60, 70, 80

Therefore:

20 < 30 < 40 < 50 < 60 < 70 < 80

The ordering is recursively maintained throughout the tree.

4.10.3BST Node

A BST node can be represented using the same structure as a binary-tree node:

class TreeNode:
    def __init__(self, value):
        self.value = value

• self.left = None
• self.right = None
• Create the root:
• root = TreeNode(50)

4.10.4Searching in a BST

• Searching is the most important advantage of a BST.
• Suppose we have:
• 50

/ \

30 70

/ \ / \

20 40 60 80

• We want to find:
• 60
• Start at 50.
• Since:
• 60 > 50
• we go right.
• 50

\

70

/

• 60
• Now:
• 60 < 70

so go left.

We find 60.

Instead of examining every node, we eliminate an entire subtree at every step.

4.10.5BST Search Algorithm

def search(root, target):
if root is None:
return False
if root.value == target:
return True
if target < root.value:
return search(root.left, target)
return search(root.right, target)

Example:

print(search(root, 60))

Output:

True

4.10.6Iterative BST Search

The same operation can be implemented without recursion:

def search(root, target):
current = root
while current:
if current.value == target:
return True
if target < current.value:
current = current.left
else:
current = current.right
return False

This avoids recursion stack usage.

4.10.7BST Search Complexity

• The complexity depends on the height of the tree.
• Time = O(h)
• where h is the height.
• For a balanced BST:
• h = O(log n)

Therefore:

Search = O(log n)

For a completely skewed BST:

h = O(n)

Therefore:

Search = O(n)

This distinction is extremely important.

4.10.8Inserting into a BST

• To insert a value, we follow the BST ordering rule.
• Consider:
• 50

/ \

30 70

• Insert:
• 40
• Since:
• 40 < 50
• go left.
• Then:
• 40 > 30
• go right.
• So:
• 50

/ \

30 70

\

40

4.10.9BST Insert Algorithm

def insert(root, value):
    if root is None:
        return TreeNode(value)
        if value < root.value:
            root.left = insert(root.left, value)

elif value > root.value:
    root.right = insert(root.right, value)

return root

Usage:

root = None

for value in [50, 30, 70, 20, 40, 60, 80]:
root = insert(root, value)

Result:

50

/ \

30 70

/ \ / \

20 40 60 80

4.10.10BST Insertion Complexity

Insertion follows one path from root to the insertion location.

Therefore:

• Time = O(h)
• Balanced:
• O(log n)
• Skewed:

O(n)

4.10.11Handling Duplicate Values

• A BST needs a rule for duplicate values.
• Common strategies include:
• Strategy 1 — Ignore duplicates

if value < root.value:

...

elif value > root.value:

...

• Equal values are ignored.
• Strategy 2 — Store duplicates on the left
• value <= node
• Strategy 3 — Store duplicates on the right
• value >= node
• Strategy 4 — Store a count
• Instead of creating multiple nodes:
• Node:

value = 50
count = 3

The appropriate strategy depends on the application.

4.10.12Inorder Traversal of a BST

One of the most important BST properties is:

• Inorder traversal produces values in sorted order.
• Consider:
• 50

/ \

30 70

/ \ / \

20 40 60 80

• Inorder:
• 20 30 40 50 60 70 80
• Recall:
• Inorder:
• Left → Node → Right

This is why inorder traversal is extremely important for BST problems.

4.10.13Getting Sorted Values from a BST

def inorder(root, result):
    if root is None:
        return

• inorder(root.left, result)
• result.append(root.value)
• inorder(root.right, result)
• Usage:

result = []

inorder(root, result)

print(result)

Output:

A BST can therefore act as an ordered data structure.

4.10.14Finding Minimum Value

In a BST, the minimum value is always located at the leftmost node.

Example:

50

/

30

/

20

/

• 10
• Minimum:
• 10
• Algorithm:

def find_min(root):
if root is None:
return None
current = root
while current.left:
current = current.left
return current.value

Complexity:

O(h)

4.10.15Finding Maximum Value

Similarly, the maximum value is at the rightmost node.

def find_max(root):
if root is None:
return None
current = root
while current.right:
current = current.right
return current.value

Complexity:

O(h)

Balanced BST:

O(log n)

4.10.16BST Deletion

• Deletion is the most complicated basic BST operation.
• There are three major cases:
• Delete a leaf node.
• Delete a node with one child.
• Delete a node with two children.

4.10.17Case 1 — Delete a Leaf Node

Consider:

50

/ \

30 70

/

• 20
• Delete:
• 20

Since 20 has no children, simply remove it:

50

/ \

30 70

This is the simplest deletion case.

4.10.18Case 2 — Delete a Node with One Child

Consider:

50

/

30

/

• 20
• Delete:
• 30
• Node 30 has one child:
• 20
• Replace 30 with 20:
• 50

/

20

4.10.19Case 3 — Delete a Node with Two Children

Consider:

50

/ \

30 70

/ \ / \

20 40 60 80

• Delete:
• 50
• The node has two children.

A common strategy is to replace it with its:

• Inorder successor
• The inorder successor is the smallest value in the right subtree.
• Right subtree:
• 70

/ \

60 80

• Smallest value:
• 60
• Replace 50 with 60:
• 60

/ \

30 70

/ \ \

20 40 80

Then remove the original 60.

4.10.20Inorder Successor

• The inorder successor of a node is the next larger value in sorted order.
• For:
• 20 30 40 50 60 70 80
• the successor of 50 is:
• 60

If the node has a right subtree, the successor is usually the leftmost node in that right subtree.

4.10.21Inorder Predecessor

• The inorder predecessor is the next smaller value.
• For:
• 20 30 40 50 60 70 80
• the predecessor of 50 is:
• 40

If the node has a left subtree, the predecessor is usually the rightmost node in that left subtree.

4.10.22BST Delete Implementation

def delete(root, value):
    if root is None:
        return None
        if value < root.value:
            root.left = delete(root.left, value)

elif value > root.value:
    root.right = delete(root.right, value)

else:
    # Case 1 and Case 2

if root.left is None:
return root.right
if root.right is None:
return root.left

# Case 3: two children

successor = root.right

while successor.left:
successor = successor.left

• root.value = successor.value
• root.right = delete(
• root.right,
• successor.value

)

return root

Complexity:

O(h)

4.10.23BST Complexity

For a BST with height h:

Balanced BST:

h = O(log n)

Therefore:

• Search → O(log n)
• Insert → O(log n)
• Delete → O(log n)
• Worst-case skewed BST:

h = O(n)

Therefore:

• Search → O(n)
• Insert → O(n)
• Delete → O(n)

4.10.24Best, Average and Worst Cases

BST performance depends heavily on tree shape.

Best Case

A very balanced structure:

50

/ \

30 70

Height is small.

Average Case

For reasonably distributed insertions, performance can often be around:

O(log n)

but the exact behavior depends on the insertion sequence and assumptions.

Worst Case

• Insert sorted values:
• 10
• 20
• 30
• 40
• 50
• The tree becomes:
• 10

\

20

\

30

\

40

\

50

Now:

h = O(n)

and operations degrade to:

O(n)

4.10.25Why Sorted Insertion Is Dangerous

• Suppose we insert:
• 10, 20, 30, 40, 50, 60
• The BST becomes:
• 10

\

20

\

30

\

40

\

50

\

60

It has effectively become a linked list.

Therefore, a basic BST does not automatically guarantee O(log n) performance.

4.10.26Balanced Binary Search Trees

• To prevent severe skewing, specialized self-balancing BSTs are used.
• Important examples:
• AVL Tree
• Red-Black Tree
• They maintain height close to:
• O(log n)

Therefore, operations remain approximately:

• Search → O(log n)
• Insert → O(log n)
• Delete → O(log n)

These structures are especially important in systems that need reliable ordered-map/set performance.

4.10.27AVL Tree

• An AVL Tree is a self-balancing Binary Search Tree.
• For every node:
• |height(left) - height(right)| ≤ 1

If an insertion or deletion makes the tree unbalanced, rotations are performed.

Example:

10

\

20

\

30

This is unbalanced.

An AVL rotation can transform it into:

20

/ \

10 30

The tree becomes balanced.

4.10.28Red-Black Tree

• A Red-Black Tree is another self-balancing BST.
• Each node has an additional color:
• Red
• Black

The tree follows specific coloring rules that ensure its height remains O(log n).

Red-Black Trees are widely used in implementations of ordered maps and sets in various programming languages and libraries.

4.10.29BST Rotations

• Rotations are local restructuring operations used to maintain balance.
• Right Rotation
• Before:
• 30

/

20

/

• 10
• After right rotation:
• 20

/ \

10 30

• Left Rotation
• Before:
• 10

\

20

\

• 30
• After:
• 20

/ \

10 30

Rotations preserve the BST ordering property.

4.10.30Kth Smallest Element

Because inorder traversal of a BST is sorted, the kth smallest element can be found using inorder traversal.

Example:

• 20 30 40 50 60 70 80
• The:
• 1st smallest = 20
• 2nd smallest = 30
• 3rd smallest = 40
• Implementation:

def kth_smallest(root, k):
    stack = []
    current = root
    while True:
        while current:
            stack.append(current)

current = current.left
current = stack.pop()

k -= 1

if k == 0:
return current.value
current = current.right

This is a very common interview problem.

4.10.31Kth Largest Element

Similarly, reverse inorder traversal gives values from largest to smallest:

Right → Node → Left

Example:

80 70 60 50 40 30 20

The kth largest can therefore be found efficiently using reverse inorder traversal.

4.10.32Validate a BST

• A common interview problem asks:
• Is this binary tree actually a valid BST?
• Consider:
• 10

/ \

5 15

/ \

6 20

This is not a valid BST.

Why?

Because 6 is in the right subtree of 10, but:

6 < 10

Simply comparing each node with its immediate parent is not sufficient.

4.10.33Valid BST Using Bounds

A robust approach passes valid minimum and maximum bounds.

def is_valid_bst(root, low=float("-inf"), high=float("inf")):
    if root is None:
        return True
        if not (low < root.value < high):
            return False
            return (
                is_valid_bst(root.left, low, root.value)
                and is_valid_bst(root.right, root.value, high)
            )

Complexity:

Time = O(n)

Space = O(h)

This is an important recursive pattern.

4.10.34BST as a Sorted Set

• A BST can be used conceptually to maintain a collection of unique values while preserving sorted order.
• For example:
• Insert:
• 50, 20, 70, 10, 30
• Inorder traversal produces:
• 10 20 30 50 70

This makes BSTs useful when we need:

• Ordered data
• Search
• Insert
• Delete
• Minimum/maximum
• Predecessor/successor

4.10.35Predecessor and Successor

For:

50

/ \

30 70

/ \ / \

20 40 60 80

For 50:

Predecessor = 40
Successor   = 60

These operations are important in ordered data structures.

4.10.36Range Search

• Suppose we want all values between:
• 35 and 65
• in:
• 50

/ \

30 70

/ \ / \

20 40 60 80

The values are:

40, 50, 60

A BST lets us skip subtrees that cannot contain values in the desired range.

This can be much more efficient than scanning every node, depending on tree balance and the size of the output.

4.10.37BST and Recursion

BST algorithms naturally follow the recursive structure:

Node

/ \

Smaller Larger

For searching:

or:

This is why recursion is particularly natural for BSTs.

4.10.38BST and Inorder Traversal

This relationship is worth memorizing:

If:

BST = 50, 30, 70, 20, 40, 60, 80

then:

Inorder = 20, 30, 40, 50, 60, 70, 80

• This property is used in:
• Kth smallest
• Kth largest
• BST validation
• Sorted output
• Predecessor/successor
• Range queries

4.10.39Building a Balanced BST from a Sorted Array

Suppose we have:

Choosing the middle element as the root:

4

/ \

2 6

/ \ / \

1 3 5 7

produces a balanced BST.

Implementation:

def sorted_array_to_bst(numbers):
if not numbers:
return None
middle = len(numbers) // 2
root = TreeNode(numbers[middle])

root.left = sorted_array_to_bst(

numbers[:middle]

)

root.right = sorted_array_to_bst(

numbers[middle + 1:]

)

return root

Complexity with slicing:

can involve extra copying. An index-based implementation avoids that extra copying and achieves:

Time = O(n)

Space = O(log n)

for a balanced result, excluding the output tree itself.

4.10.40BST Applications

• BSTs are useful when applications require ordered data with dynamic updates.
• Examples include:
• Ordered sets
• Ordered maps
• Symbol tables
• Searching
• Range queries
• Scheduling
• Maintaining sorted data
• Predecessor/successor queries
• Database/indexing concepts

Self-balancing variants are particularly useful when predictable logarithmic performance is required.

4.10.41BST in Database Systems

Database indexes often use tree-based structures, although practical database systems commonly use B-Trees or B+ Trees rather than ordinary binary search trees.

The fundamental idea is similar:

For example:

Find customer ID = 105023

An index can avoid scanning every record.

This is one reason tree-based indexing is fundamental in database systems.

4.10.42BST vs Hash Table

This is an important interview comparison.

• Use a hash table when:
• Fast exact key lookup is the main requirement.
• Use a BST/ordered tree when:
• Ordering, ranges, predecessor/successor, or sorted traversal matter.

4.10.43BST vs Heap

A heap is primarily designed for priority queues.

A BST is designed for ordered searching.

4.10.44Common BST Interview Problems

Beginner

• Search in a BST.
• Insert into a BST.
• Find minimum.
• Find maximum.
• Inorder traversal.
• Find predecessor.
• Find successor.
• Calculate height.

Intermediate

• Delete a node.
• Validate BST.
• Kth smallest element.
• Kth largest element.
• Lowest Common Ancestor in BST.
• Range Sum of BST.
• Search for a value range.
• Convert sorted array to BST.
• Find closest value.
• Find floor and ceiling.

Advanced

• Construct BST from preorder.
• Recover a corrupted BST.
• Serialize and deserialize BST.
• Balance an unbalanced BST.
• Trim a BST.
• Merge two BSTs.
• Two Sum in a BST.
• Find median in a BST.

Convert BST to sorted doubly linked list.

Implement an iterator for BST.

4.10.45Important BST Interview Pattern: Two Sum

Given a BST:

5

/ \

3 6

/ \ \

2 4 7

• Target:
• 9
• Possible pair:
• 2 + 7 = 9
• One approach is:

This combines BST traversal with the Two Pointers pattern.

4.10.46Important BST Interview Pattern: Floor

The floor of a target is the greatest value in the BST that is less than or equal to the target.

• Suppose:
• Values:
• 10, 20, 30, 40, 50
• For:

target = 35

• the floor is:
• 30
• For:

target = 40

the floor is:

40

BST ordering allows us to find the answer efficiently.

4.10.47Important BST Interview Pattern: Ceiling

• The ceiling is the smallest value greater than or equal to the target.
• For:
• Values:
• 10, 20, 30, 40, 50
• and: