## 94. Binary Tree Inorder Traversal

Given a binary tree, return the inorder traversal of its nodes' values.

For example:
Given binary tree `[1,null,2,3]`,

```   1
\
2
/
3
```

return `[1,3,2]`.

Note: Recursive solution is trivial, could you do it iteratively?

b'
\n\n

## Solution

\n
\n

#### Approach #1 Recursive Approach [Accepted]

\n

The first method to solve this problem is using recursion.\nThis is the classical method and is straightforward. We can define a helper function to implement recursion.

\n\n

Complexity Analysis

\n
\n
• \n

Time complexity : . The time complexity is because the recursive function is .

\n
• \n
• \n

Space complexity : The worst case space required is , and in the average case it\'s where is number of nodes.

\n
• \n
\n
\n

#### Approach #2 Iterating method using Stack [Accepted]

\n

The strategy is very similiar to the first method, the different is using stack.

\n

Here is an illustration:

\n

!?!../Documents/94_Binary.json:1000,563!?!

\n\n

Complexity Analysis

\n
\n
• \n

Time complexity : .

\n
• \n
• \n

Space complexity : .

\n
• \n
\n
\n

#### Approach #3 Morris Traversal [Accepted]

\n

In this method, we have to use a new data structure-Threaded Binary Tree, and the strategy is as follows:

\n
\n

Step 1: Initialize current as root

\n

Step 2: While current is not NULL,

\n

If current does not have left child

\n

\n

b. Go to the right, i.e., current = current.right

\n

Else

\n

a. In current\'s left subtree, make current the right child of the rightmost node

\n

b. Go to this left child, i.e., current = current.left

\n
\n

For Example:

\n
`          1\n        /   \\\n       2     3\n      / \\   /\n     4   5 6\n`
\n

First, 1 is the root, so initialize 1 as current, 1 has left child which is 2, the current\'s left subtree is

\n
`         2\n        / \\\n       4   5\n`
\n

So in this subtree, the rightmost node is 5, then make the current(1) as the right child of 5. Set current = cuurent.left (current = 2).\nThe tree now looks like:

\n
`         2\n        / \\\n       4   5\n            \\\n             1\n              \\\n               3\n              /\n             6\n`
\n

For current 2, which has left child 4, we can continue with thesame process as we did above

\n
`        4\n         \\\n          2\n           \\\n            5\n             \\\n              1\n               \\\n                3\n               /\n              6\n`
\n

then add 4 because it has no left child, then add 2, 5, 1, 3 one by one, for node 3 which has left child 6, do the same as above.\nFinally, the inorder taversal is [4,2,5,1,6,3].

\n

For more details, please check \nThreaded binary tree and \nExplaination of Morris Method

\n\n

Complexity Analysis

\n
\n
• \n

Time complexity : . To prove that the time complexity is ,\nthe biggest problem lies in finding the time complexity of finding the predecessor nodes of all the nodes in the binary tree.\nIntuitively, the complexity is , because to find the predecessor node for a single node related to the height of the tree.\nBut in fact, finding the predecessor nodes for all nodes only needs time. Because a binary Tree with nodes has edges, the whole processing for each edges up to 2 times, one is to locate a node, and the other is to find the predecessor node.\nSo the complexity is .

\n
• \n
• \n

Space complexity : . Arraylist of size is used.

\n
• \n
\n
\n

Analysis written by: @monkeykingyan

\n
'