The ultimate guide to Big-O notation for coding interviews, developed by FAANG engineers. Learn algorithm complexity in simple terms and get interview-ready in just a few hours.

This course is intended for professionals that lack formal education in computer science, and that are in search of a simple and practical guide to algorithmic complexity. The course explains the concepts in layman's terms, and teaches how to reason about the complexity of algorithms without requiring one to have an extensive mathematical skillset. This course can also be handy for revising complexity concepts or Big-O analysis before interviews. Finally, the content also scratches the surface of some advanced analysis topics to provide a more encompassing image of the complexity theory.

Big-O Notation For Coding Interviews and Beyond

In this lesson we won't attempt to describe various tree data-structures and their associated operations. Rather, we'll do a general discussion on how to reason and think about space and time complexity when tree structures are involved.

<h2>Tree Traversals</h2>
When traversing a tree, does the size of the tree affect how much time it takes for you to go through every node of the tree? Yes, it does. A bigger tree will take more time to go through than a smaller tree. The following recursive algorithms for tree traversals all take O(n) time since we are required to visit each node.

<ul>
<li>pre-order traversal</li>
<li>in-order traversal</li>
<li>post-order traversal</li>
<li>depth first search. Note the above three algorithms are types of depth first traversals</li>
<li>breadth first traversal/search</li>
</ul>

For the above algorithms, the more interesting question pertains to space complexity for the above algorithms. Since one can write these algorithms recursively, it's not immediately clear what the space complexity is. A novice may think it is constant when it is not. Look at the code below:

```java
 class TreeNode {
 TreeNode left;
 TreeNode right;
 int val;
 }

 void recursiveDepthFirstTraversal(TreeNode root) {
 if (root == null)
 return;

 recursiveDepthFirstTraversal(root.left);
 System.out.println(root.val);
 recursiveDepthFirstTraversal(root.right);
 }
```

A naive look at the <code class="mthd">recursiveDepthFirstTraversal</code> method may mislead you to think that there's no extra space being used. However, behind the scenes, the recursive calls are stored on a stack by the underlying language platform. When we implement the non-recursive version then we are better able to appreciate the space requirements. Take a look at the non-recursive version of in-order traversal below:

```java
 void depthFirstTraversal(TreeNode root) {

1. Stack<TreeNode> stack = new Stack<>();
2. TreeNode trav = root;
3. 
4. while (trav != null || !stack.isEmpty()) {
5. 
6. while (trav != null) {
7. stack.push(trav);
8. trav = trav.left;
9. }
10.
11. trav = stack.pop();
12. System.out.println(trav.val);
13.
14. trav = trav.right;
 }
 }
```

Now it should be apparent that the algorithm relies on the use of a stack. It is either implicit in case of recursion or explicit if an iterative version is written out.

<h2>Tree Traversals</h2>
When traversing a tree, does the size of the tree affect how much time it takes for you to go through every node of the tree? Yes, it does. A bigger tree will take more time to go through than a smaller tree. The following recursive algorithms for tree traversals all take O(n) time since we are required to visit each node.

<ul>
<li>pre-order traversal</li>
<li>in-order traversal</li>
<li>post-order traversal</li>
<li>depth first search. Note the above three algorithms are types of depth first traversals</li>
<li>breadth first traversal/search</li>
</ul>

For the above algorithms, the more interesting question pertains to space complexity for the above algorithms. Since one can write these algorithms recursively, it's not immediately clear what the space complexity is. A novice may think it is constant when it is not. Look at the code below:

```java
 class TreeNode {
 TreeNode left;
 TreeNode right;
 int val;
 }

 void recursiveDepthFirstTraversal(TreeNode root) {
 if (root == null)
 return;

 recursiveDepthFirstTraversal(root.left);
 System.out.println(root.val);
 recursiveDepthFirstTraversal(root.right);
 }
```

A naive look at the <code>recursiveDepthFirstTraversal</code> method may mislead you to think that there's no extra space being used. However, behind the scenes, the recursive calls are stored on a stack by the underlying language platform. When we implement the non-recursive version then we are better able to appreciate the space requirements. Take a look at the non-recursive version of in-order traversal below:

```java
 void depthFirstTraversal(TreeNode root) {

1. Stack<TreeNode> stack = new Stack<>();
2. TreeNode trav = root;
3. 
4. while (trav != null || !stack.isEmpty()) {
5. 
6. while (trav != null) {
7. stack.push(trav);
8. trav = trav.left;
9. }
10.
11. trav = stack.pop();
12. System.out.println(trav.val);
13.
14. trav = trav.right;
 }
 }
```

Now it should be apparent that the algorithm relies on the use of a stack. It is either implicit in case of recursion or explicit if an iterative version is written out.

This lesson is a general discussion on reasoning about space and time complexity of tree structures

Basics

Formal Analysis Tools

Recursive

Data-Structures

Amortized Analysis

Probabilistic Analysis

Complexity Theory

The End

Tree Structures