path[] traverse(root): Input root of a binary tree if root = NULL then return end if traverse(left(root)) add root to path traverse(right(root)) return

Complexity

Time complexity: $O(n)$.

Every node in the binary tree will be visited once.

Space complexity: $O(n)$.

In the worst case (all nodes in the tree only have left or right subtrees), the length of the function call stack will be $n$.

Goes to the leftmost node in the tree while pushing the nodes onto a stack.

After reaching the leftmost node, pop a node from the stack and visit it, then move to its right subtree.

Repeat until all nodes are visited.

Pseudocode of this approach:

1 2 3 4 5 6 7 8 9 10 11 12 13 14

inorderTraversal(root): Input root of a binary tree path[] st = empty stack while p != NULL and st is not empty do while p != NULL do push p onto st p = left(p) end while pop p from st add p to path p = right(p) end while

Complexity

Time complexity: $O(n)$.

$n$ loops in total to visit every node once.

Space complexity: $O(n)$.

In the worst case, the length of the stack will be $n$.

inorderTraversal(root): Input root of a binary tree path[] p = root while p != NULL do if left(p) == null then add p to path // Move to its right subtree p = right(p) else // pre is the predecessor of p pre = left(p) // Find the rightmost node in the right subtree while right(p) != NULL do pre = right(pre) end while // Put p after pre right(pre) = p // Unlink the original left subtree from the binary tree parent = p p = left(p) left(parent) = NULL end if end while