Leetcode Problem 94 Binary Tree Inorder Traversal.txt

94. Binary Tree Inorder Traversal
Given a binary tree, return the inorder traversal of its nodes' values.

Example:

Input: [1,null,2,3]
   1
    \
     2
    /
   3

Output: [1,3,2]
Follow up: Recursive solution is trivial, could you do it iteratively?



Iterative solution hint: Use a stack. Keep on appending until there is left child available.
When left child is empty then pop from the stack and append the value.
If right child is present make the current iteration node right node. In next iterative call this will be automatically appended to the stack.


# Definition for a binary tree node.
# class TreeNode:
#     def __init__(self, x):
#         self.val = x
#         self.left = None
#         self.right = None

class Solution:
    
    def inorderRecursive(self, node: TreeNode):
        if not node:
            return
        
        self.inorderRecursive(node.left)
        self.result.append(node.val)
        self.inorderRecursive(node.right)
    
    def inorderIterative(self, node:TreeNode):
        
        stack = []
        
        while stack or node:
            while node:
                stack.append(node)
                node=node.left
                
            temp = stack.pop()
            self.result.append(temp.val)
            
            if temp.right:
                node = temp.right
            
            
            
    
    
    def inorderTraversal(self, root: TreeNode) -> List[int]:
        self.result = []
        #self.inorderRecursive(root)
        
        self.inorderIterative(root)
        return self.result