Binary Tree Inorder Traversal

LeetCode Q 94 - Binary Tree Inorder Traversal

Given a binary tree, return the inorder traversal of its nodes’ values.

Follow up: Recursive solution is trivial, could you do it iteratively?

Similar Questions: Preorder Traversal, Postorder Traversal

Solution

Code:

public List<Integer> inorderTraversal(TreeNode root) {
	List<Integer> res = new ArrayList<>();
	if (root == null) return res;

	Stack<TreeNode> stack = new Stact<>();
	TreeNode curr = root;
	while (curr != null || !stack.isEmpty()) {
		while (curr != null) { stack.push(curr); curr = curr.left; }
		curr = stack.pop();
		res.add(curr.val);
		curr = curr.right;
	}

	return res;
}