Leetcode 144 Binary Tree Preorder Traversal

Leetcode 144 Binary Tree Preorder Traversal

The problem description is as follow:

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

For example:
Given binary tree {1,#,2,3},
1
\
2
/
3
return [1,2,3].```

In case you are not familiar with preorder tree traversal, the following graph would help: The preorder traversal for previous tree is `F, B, A, D, C, E, G, I, H`.

Recursive Approach Edit Binary Tree Preorder Traversal on GitHub

Recursive approach is pretty straight forward. The order of preorder is :

```1. Parent Node
2. Left Child
3. Right Child```

Thus the code will be:

```/**
* Definition for a binary tree node.
* public class TreeNode {
*     int val;
*     TreeNode left;
*     TreeNode right;
*     TreeNode(int x) { val = x; }
* }
*/
public class Solution {
public List<Integer> preorderTraversal(TreeNode root) {
List<Integer> result=new ArrayList<Integer> ();

if (root==null){
return result;
}
builder(root, result);
return result;
}
private void builder(TreeNode root, List<Integer> result){
if (root==null){
return;
}
builder(root.left, result);
builder(root.right, result);
}
}```

The time complexity of recursive approach is `O(n)` since we are just traversing the whole tree once. The space complexity of recursive approach is `O(log n)`.

Iterative Approach Edit Binary Tree Preorder Traversal on GitHub

When it comes to iterative approach in tree traversal, always use a stack or queue. We could use a stack to imitate the recursive process we did above:

```public class Solution {
public List<Integer> preorderTraversal(TreeNode root) {
List<Integer> res = new ArrayList<Integer>();
if(root == null)
return res;
TreeNode q = root;
while(q!=null || !stack.isEmpty()) {
if(q!=null) {
stack.push(q);
q = q.left;
}
else {
q = stack.pop();
q = q.right;
}
}
return res;
}
}```

The time complexity of recursive approach is `O(n)` since we are just traversing the whole tree once. The space complexity of recursive approach is `O(log n)`.

Morris Traversal Algorithm Edit Binary Tree Preorder Traversal on GitHub

Actually there’s a better way to solve the problem. Instead of using `O(log n)` space, we could solve it with `O(l)` space.

In order to solve the problem with `O(l)` space, the most important question is how to traverse back to parent node from child node. Morris traversal introduce threaded binary tree. In threaded binary tree, we don’t have to assign additional space to every node pointing to the predecessor and successor, nor do we have to save the nodes into stack.

```1. If left child of current node is empty, output current node. Set current's right child as current node
2. If left child of current node is not empty, find the in-order traversal predecessor node in its left subtree
- If predecessor's right child is empty, set predecessor's right child = current node. Output current node. Set current node = current node's left child.
- If predecessor's right child is current node, set predecessor's right child back to empty (recover structure of tree). Set current node = current node's right child.
- There won't be other possibility according to definition of predecessor.

Repeat process 1 and 2 until current node is empty.```

The following graph would help a lot: Here comes the code:

```public class Solution {
public List<Integer> preorderTraversal(TreeNode root) {
List<Integer> res = new ArrayList<Integer>();
TreeNode cur = root;
TreeNode pre = null;
while(cur != null)
{
if(cur.left == null) {
cur = cur.right;
}
else {
pre = cur.left;
while(pre.right!=null && pre.right!=cur)
pre = pre.right;
if(pre.right==null) {
pre.right = cur;
cur = cur.left;
}
else {
pre.right = null;
cur = cur.right;
}
}
}
return res;
}
}```

Since we are traversing each node at most twice, the time complexity is still `O(n)` and we are only using `O(1)` extra space.