Binary Tree Inorder Traversal
Tags: webdev, beginners, programming, python
Published: 2022-01-30 01:27:50


![Illustration from "The Giving Tree" by Shell Silverstein. The image includes the tree and it's leaves falling for the boy to catch them.](https://dev-to-uploads.s3.amazonaws.com/uploads/articles/5ljtmxkkecjpolvcg08f.jpeg)
Branching out with another Leetcode Binary Tree challenge! This is the first time I'm learning about inorder traversal, so I was excited to understand the process! Like almost all of the LeetCode questions, the directions can be deceiving. We are given a challenge: Given the root of a binary tree, return the inorder traversal of its nodes' values.

If you're new to binary tree's like me, I had a false sense of what inorder meant. Understanding the pattern of inorder traversal will enlighten us on how to go about solving this problem. 

Inorder traversal goes in the order of left, root, then right. 

Let's apply this to our first example to understand our input.  

![Binary tree with a root of one. No left node, right node of 2.Node 2 has a left node of 3](https://dev-to-uploads.s3.amazonaws.com/uploads/articles/b5ee6n6sbyz7pql9r3gb.png)

In the example above, we start with node 1. There is no left node, so we go back to the root which is 1. Then we proceed to the right to node 2. We repeat the pattern (from node 2)by looking to the left root (in the example being 3) followed by the right root. This gives us the output [ 1, 3, 2]. 

For this solution, we are going to solve it recursively. This means we want to keep track of base case and recursive case. Base case means when we make the return/ when we exit the function. 

Here is out starter code: 

```python
class Solution:
    def inorderTraversal(self, root: Optional[TreeNode]) -> List[int]:

```
For our base case, if the root is none then we will exit our function. Since our output is a list, we want to return an empty list. 

```python
class Solution:
    def inorderTraversal(self, root: Optional[TreeNode]) -> List[int]:
      if root is None:
          return []

```
If the root is not none, then we are going to do an inorder traversal. This is done through a nifty built in function called inorderTraversal which will follow the pattern we discussed starting from the root. 

```python
class Solution:
    def inorderTraversal(self, root: Optional[TreeNode]) -> List[int]:
      if root is None:
          return []
      return self.inorderTraversal(root.left) + [root.val]+ self.inorderTraversal(root.right)

```
We add root.left as an argument because it aligns with inorder traversal where the order is left. Then we add the value of the root (in this case being node 1). And finally we call inorderTraversal with an argument of (root.right) because it's the last side we call in order. 

If we break this return value down, we are translating the inorder pattern of left, root, right and returning them into an array. 

Conclusion:
I really had no idea about inorder traversal. I thought they meant to follow the order by the chronological values like 1, 2, 3 but I was totally wrong! Not knowing the order of inorder traversal hindered me from getting very far in this problem before I ran to the internet for help. Because as much studying as I'm doing, there will always be concepts out there that will be new.