Binary Tree Inorder Traversal (Leet Code - 94)

This article is another part of a series on leet code problems solutions, and it provides a solution to the leet code problem number 94. This is a Leet code problem named Binary Tree Inorder Traversal. We will solve it using python and it is the best space and time-optimized solution.

Question of Binary Tree Inorder Traversal

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

In In-Order Traversal we simply traverse in the LNR format. In LNR format, we first read the left node, then the root node, and at last the right side of the node.

Example

Example 1

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

Example 2

Input: root = []
Output: []

Example 3

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

Constraints

The number of nodes in the tree is in the range [0, 2000].
-1000 <= Node.val <= 1000

Approach to solve Binary Tree Inorder Traversal

To solve this problem we will first visit through the left node after that we visit the root node and at last, we visit the right node in a recursive manner.

Algorithm

This method performs the following steps for a given input array:

Create nodes array to store nodes.
Create an inner function to do recursion.
Check if the root exists. If yes then go to step 4 otherwise break inner function.
Call left child of root recursively.
append the value of root to node variable.
Call right child of root recursively.
End if
End inner function
return node

Python Code for Binary Tree Inorder Traversal

# Definition for a binary tree node.
# class TreeNode:
#     def __init__(self, val=0, left=None, right=None):
#         self.val = val
#         self.left = left
#         self.right = right
class Solution:
    def inorderTraversal(self, root: Optional[TreeNode]) -> List[int]:

        #create list to store data
        stack = []
        def traverse(root):
            #base condition
            if root is None:
                return None
             #visit left tree
            traverse(root.left)
            #visit base node
            stack.append(root.val)
            # visit right node
            traverse(root.right)
        traverse(root)
    
        return stack