InOrder Binary Tree Traversal

InOrderBinaryTreeTraversal.java

// recursive
public List<Integer> inorderTraversal(TreeNode root) {
  List<Integer> ans = new ArrayList();
  if(root == null) return ans;
  ans.addAll(inorderTraversal(root.left));
  ans.add(root.val);
  ans.addAll(inorderTraversal(root.right));
  return ans;
}

// iterative
public List<Integer> inorderTraversal(TreeNode root) {
  List<Integer> ans = new ArrayList();
  Deque<TreeNode> stack = new LinkedList();
  while(root != null || !stack.isEmpty()) {
    while(root != null) {
      stack.push(root);
      root = root.left;
    }
    root = stack.pop();
    ans.add(root.val);
    root = root.right;
  }
  return ans;
}