LeetCode #94 Binary Tree Inorder Traversal

Medium

Problem

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?

Solution — Recursion

As problem describes, it’s trivial.

Complexity

It’s trivial that time complexity will be O(n) which n denotes to counts of node of this tree.

For space complexity, because we need h calls for reaching leaves if h denotes to path length of the longest path in this tree. Hence, space complexity is O(h). Or you can say O(logn) because h is bounded by logn.

Solution — Iteration

If we’d like to use iterative approach, it needs a help from using stack.

Complexity

Each node will be traversed once so time complexity is only O(n) if n denotes to counts of nodes in this tree.

For space complexity, using stack is just like using call stack in recursion approach. Therefore, it’s space complexity will be the same with recursion approach, which is O(h) (or O(logn)) if h denotes to path length of the longest path in this tree.