Binary In-order Traversal
Recursive Approach
class Solution {
public List<Integer> inOrderTaversal(TreeNode root){
List<Integer> result = new ArralyList<>();
inOrder(root, result);
return result;
}
public void inOrder(TreeNode root, List<Integer> result) {
if (root != null) {
inOrder(root.left, result);
result.add(root.value);
inOrder(root.right);
}
return;
}
}
Time Complexity: O(n);
Space Complexity: O(n);
Morris Traversal Approach
class Solution {
public List<Integer> inOrderTaversal(TreeNode root){
List<Integer> result = new ArrayList<>();
TreeNode current = root;
TreeNode predecessor;
while (current !=null) {
if (current.left == null) {
result.add(current.value);
current = current.right // move to next right node
} else {
// if you have left sub TreeNode
predecessor = current.left;
// find extrene rightmost node in the left subtree or node that already points to current
while (predecessor.right != null && predecessor.right!= current){
predecessor = predecessor.right
}
if (predecessor.right == null){
// Establish a temporrary thread..
predecessor.right = current;
current = current.left;
} else {
predecessor.right = null;// Restore the TreeNode
result.add(current.value); // add to current node to result...
current = current.right; // Move to the right sub tree
}
}
}
}
}
Time Complexity: O(n);
Space Complexity: O(1);