Reference: LeetCode

Difficulty: Medium

## Problem

Given a binary tree, return the

`inorder`

traversal of its nodes’ values.

**Follow up:** Recursive solution is trivial, could you do it iteratively?

## Analysis

### Recursion

1 | public List<Integer> inorderTraversal(TreeNode root) { |

**Time:** $O(N)$ since the recursive function is $T(N) = 2T(N/2) + 1$**Space:** $O(\log{N})$ (when balanced); $O(N)$ (worst).

### Iteration

**Note:**

- The condition is
`p != null || !stack.isEmpty()`

. - Notice
`p = p.right`

:- If
`p.right`

is`null`

, the next node would be the node currently in the stack. - Otherwise, the next node would be the leftmost node of the right child (after continuous pushing).

- If

**“while” version:**

1 | public List<Integer> inorderTraversal(TreeNode root) { |

**“if” version:**

1 | public List<Integer> inorderTraversal(TreeNode root) { |

**Time:** $O(N)$**Space:** $O(\log{N})$ (when balanced); $O(N)$ (worst).

### Morris Traversal

Morris Traversal (reference)

**Basic Idea:** Morris Traversal uses the idea of `threaded binary tree`

. It uses the `left`

and `right`

pointers of leaves to access the predecessor and successor in a specific traversal.

**Step:** (`p`

is the current node)

- If
`p`

‘s left child is`null`

, output`p`

and set its right child as the new`p`

. - If
`p`

‘s left child is`not null`

, then we find the`predecessor`

of`p`

in the left subtree.- If the
`predecessor`

‘s right child is`null`

, set its right child to`p`

, and update`p`

with its`left`

child. - If the
`predecessor`

‘s right child is`p`

, set its right child to`null`

(restore), and**output**and update`p`

`p`

with its`right`

child.

- If the
- Repeat the steps above until
`p`

is`null`

.

1 | public List<Integer> inorderTraversal(TreeNode root) { |

**Time:** $O(N)$

Intuitively, we may think the time complexity is $O(N\log{N})$ since finding a predecessor of a node takes $O(\log{N})$. In fact, finding all predecessors of all nodes just costs $O(N)$ time because in the whole process each edge/link is only traversed twice, the first time is to locate a node and the second time is to find the predecessor.

**Space:** $O(1)$