Leetcode: Binary Tree Inorder Traversal

Binary Tree Inorder Traversal | LeetCode OJ

There are both recursive and iterative ways to do this

Recursive

1. Initialze empty result list
2. Find output of inorder traversal of left subtree
3. Add it to result
4. Add current value to result
5. Find output of inorder traversal of right subtree
6. Add it to the result

In python everything can be done in a single line by adding lists

Since no variables are being used the recursion takes O(1) space. It is performed for all the nodes of the tree, hence runs in O(n) time

For the iterative solution we need to take the following steps

1. Move to the leftmost child of the tree and insert it in the stack
2. Stack all the nodes encountered on the way
3. Now we are at the leftmost node that would come first in the traversal
4. Pop it from the stack and add it to the result
5. Now if there is a right child, move to it and repeat
6. otherwise continue to pop nodes

Remarks:

1. O(n) time complexity, for iterating through all the nodes
2. O(n) space complexity, for storing the nodes in the stack

def inorderTraversal(self, root):
    """
    :type root: TreeNode
    :rtype: List[int]
    """
    return self.inorderTraversal(root.left) + [root.val] + self.inorderTraversal(root.right) if root else []
def inorderTraversal(self, root):
    res = []
    st = []
    node = root
    while st or node:
        if node:
            st.append(node)
            node = node.left
        else:
            node = st.pop()
            res.append(node.val)
            node = node.right
    return res