Binary Tree Inorder Traversal

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.

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:

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.

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.

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.