Solution

Approach #1 Recursive Approach [Accepted]

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.

Complexity Analysis

\n
• \n

  Time complexity : $$O(n)$$ . The time complexity is $$O(n)$$ because the recursive function is $$T(n) = 2*T(n/2)+1$$ .

  \n
\n
• \n

  Space complexity : The worst case space required is $$O(n)$$ , and in the average case it\'s $$O(log(n))$$ where $$n$$ is number of nodes.

  \n
\n

Approach #2 Iterating method using Stack [Accepted]

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

Here is an illustration:

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

Complexity Analysis

\n
• \n

  Time complexity : $$O(n)$$ .

  \n
\n
• \n

  Space complexity : $$O(n)$$ .

  \n
\n

Approach #3 Morris Traversal [Accepted]

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

\n

Step 1: Initialize current as root

\n

Step 2: While current is not NULL,

\n

If current does not have left child

\n

a. Add current\xe2\x80\x99s value

\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

For Example:

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

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

         2\n        / \\\n       4   5\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:

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

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

        4\n         \\\n          2\n           \\\n            5\n             \\\n              1\n               \\\n                3\n               /\n              6\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].

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

Complexity Analysis

\n
• \n

  Time complexity : $$O(n)$$ . To prove that the time complexity is $$O(n)$$ ,\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 $$O(nlogn)$$ , 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 $$O(n)$$ time. Because a binary Tree with $$n$$ nodes has $$n-1$$ 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 $$O(n)$$ .

  \n
\n
• \n

  Space complexity : $$O(n)$$ . Arraylist of size $$n$$ is used.

  \n
\n

Analysis written by: @monkeykingyan