# Binary Tree Inorder Traversal

This post is part of the Algorithms Problem Solving series.

## Problem description

Given the root of a binary tree, return the inorder traversal of its nodes' values

## Examples

**Example 1:**

```
Input: root = [1,null,2,3]
Output: [1,3,2]
```

**Example 2:**

```
Input: root = []
Output: []
```

**Example 3:**

```
Input: root = [1]
Output: [1]
```

**Example 4**:

```
Input: root = [1,2]
Output: [2,1]
```

**Example 5**:

```
Input: root = [1,null,2]
Output: [1,2]
```

## Solutions

The first step is to make sure we have a initial list to add elements and return as the result of our implementation. We can do this by initializing the list in when the class instance is created:

```
def __init__(self):
self.inorder_list = []
```

Then we need to verify if the tree exists or it is an "empty tree"
(basically the empty tree here is a `None`

value).

```
if root:
# The tree has nodes, do the traversal!
```

To do an inorder traversal, we need to just go to the leftmost node, add the node value, and then go to the right node. We can do this recursively:

```
class Tree:
def __init__(self):
self.inorder_list = []
def inorder_traversal(self, root):
if root:
self.inorder_traversal(root.left)
self.inorder_list.append(root.val)
self.inorder_traversal(root.right)
return self.inorder_list
```

With recursion, the algorithm looks pretty simple.

The time and space complexities are both O(n).

## Resources

- Learning Python: From Zero to Hero
- Algorithms Problem Solving Series
- Stack Data Structure
- Queue Data Structure
- Linked List
- Tree Data Structure

Have fun, keep learning, and always keep coding!