Leetcode 94. Binary Tree Inorder Traversal (Python)

Related Topic

Depth-First-Search. Tree. Inorder-Traversal.

Description

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

Sample I/O

Example 1

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

Output: [1,3,2]

Follow up

Recursive solution is trivial, could you do it iteratively?

Methodology

This question can be solved by Depth First Search.

This is very direction answer, you can apply dfs directly. However, for the follow up question, to solve it iteratively, you can use stack.

Code 1 (DFS)

def inorderTraversal(self, root: TreeNode) -> List[int]:
        if root is None: return []
        def dfs(root,res):
            if root is None: return
            dfs(root.left,res)
            res.append(root.val)
            dfs(root.right,res)
            return res
        return dfs(root,[])

BigO

We traversal all nodes of the tree once so O(n)

Code 2 (Iteratively)

def inorderTraversal(self, root: TreeNode) -> List[int]:
        stack = [root]
        res = []
        while stack:
            node = stack.pop()
            if node:
                stack.append(node.right)
                stack.append(node)
                stack.append(node.left)
            else:
                if stack:
                    node = stack.pop()
                    res.append(node.val)

BigO

We traversal all nodes of the tree once so total time complexity is O(n)