inOrderTraversal.py

# Binary Tree Inorder Traversal

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

 # https://assets.leetcode.com/uploads/2020/09/15/inorder_1.jpg
 # https://assets.leetcode.com/uploads/2020/09/15/inorder_5.jpg
 # https://assets.leetcode.com/uploads/2020/09/15/inorder_4.jpg
 

# 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]
 

# Constraints:

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

# Follow up:

# Recursive solution is trivial, could you do it iteratively?

# 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: TreeNode) -> List[int]:
        
        #Iterative  Solution:
        if root is None:
            return []
        
        retList = []
        current = root  
        stack = [] # initialize stack 
        
        while True: 
          
            if current is not None: 
                stack.append(current)
                current = current.left  
            elif(stack): 
                current = stack.pop() 
                print(current.val, end=" ") # Python 3 printing 
                retList.append(current.val)
                current = current.right  
            else: 
                break
        
        
        return retList
        
#         if root is None:
#             return []
        
        
#         retList = []
        
#         if root.left is not None:retList += self.inorderTraversal(root.left)
#         retList += [root.val]
#         if root.right is not None: retList += self.inorderTraversal(root.right)
        
#         return retList