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
Complexity Analysis
Time Complexity: O(n)
n is the number of nodes in the binary tree.
Space Complexity: O(n)
n is the number of nodes in the binary tree.
So here is the end of the post. If you find any issues or any questions then write a comment. Share with your friends.