LeetCode #144 Binary Tree Preorder Traversal

Medium

Problem

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

Example:

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

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

Use a stack for help in iterative approach.

Complexity

The same with recursive approach. It needs O(n) time if n denotes to counts of nodes in this tree, because each node will only be visited once.

For space complexity, the stack in this approach needs extra space just like call stack in recursion approach. Therefore, it’s space complexity is O(h) (or O(logn)) if h denotes to the longest path from root to leaves.