Depth-First Search - Postorder Traversal of a Binary Tree

Intro

The Postorder traversal is another strategy of the Depth-First Search algorithm.
In the previous posts, we covered the Preorder and Inorder traversals of a Binary Tree.

Here, we will go through and understand the Postorder traversal and see how we can implement it.

 Depth-First Search - Inorder Traversal of a Binary Tree

Intro

In the previous post, we covered the Preorder traversal of a Binary Tree, and here, we'll go through one more DFS strategy of a tree traversal: Inorder Traversal. It is similar to the Preorder, just the order in which we visit the nodes is a bit different.

Depth-First Search - Preorder Traversal of a Binary Tree

Intro

In the previous post, we've covered the Depth-First Search algorithm.
We said that there are three strategies for the DFS traversal: Preorder, Inorder, and Postored. In this post, we'll cover the Preorder traversal of a Binary Tree.

 Depth-First Search

Intro

There are two ways to traverse the tree data structure: Breadth-first search (BFS) and Depth-First Search (DFS).

We've already covered the BFS and Order Lever traversal of a Binary Tree. Here, we will explore the Depth-First Search algorithm and the ways we can traverse the tree using it.

 Breadth-First Search (Level Order Traversal)

Intro

We use the Breadth-First Search algorithm to traverse the Tree data structures. It is usually used when we want to determine if some value is present in the Binary Tree.

 Binary Search

Intro

Binary search is an efficient divide-and-conquer algorithm for finding an item from a sorted list of items.
It has a time complexity of O(n log n).

 Linear Search

Intro

Linear search is a fairly simple searching algorithm with a time complexity of O(n).
It is a well-suited algorithm for small datasets. It can be used for both sorted and unsorted datasets.

 Sorting algorithms - Questions and answers

Here are some good examples of the questions that we might be asked during the coding interview.

 Comparison of Sorting Algorithms - in-depth analysis

Let's go through and compare the five most famous algorithms, that we already covered in previous posts:

 Quick Sort

Intro

Quick sort is an efficient sorting algorithm, that is based on the divide and conquer approach.
Just like with the Merge sort, it divides the array into smaller sub-arrays and applies the solution to the smaller parts first.
It has a time complexity of O(n log n) - the same as Merge sort.

 Merge Sort

Intro

Merge sort is an efficient divide-and-conquer sorting algorithm that has a time complexity of O(n log n).

A divide-and-conquer algorithm recursively breaks down a problem into two or more sub-problems, until they become simple enough to be solved directly.

Insertion Sort

Intro

Insertion sort is one of the three famous algorithms (Bubble Sort, Selection Sort, and Insertion Sort) that have a time complexity of O(n^2), which means it is not a fast sorting algorithm.

Let's see how it works and its implementation.

 Selection sort

Intro

Selection sort fits into the group of the slowest sorting algorithms (together with Bubble sort and Insertion sort) with the time complexity of the O(n^2).

It is one of the slowest algorithms because we need to write nested loops, just like we did in the Bubble sort. 

Bubble Sort

Intro

Bubble sort - one of the slowest sorting algorithms. But let's see why.

It has a time complexity of O(n^2) (n squared). Why?
Because to implement it, we need to use a nested loop. It means we will have a loop inside another loop. That's because, in bubble sort, we need to compare one element with every (almost every) other element and swap them if necessary.