Table of contents


Given problem

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

For example: 
Input: [1,null,2,3]
   1
    \
     2
    /
   3

Output: [1,3,2]


Using recursive version

public void inorderTraversal(TreeNode root, List<Integer> res) {
    if (root == null) {
        return;
    }

    inorderTraversal(root.left, res);
    res.add(root.val);
    inorderTraversal(root.right, res);
}


Using iterative version

Some steps for the iterative version:

  • First, we will get all elements from the left side of the specific element, push them into the stack.
  • Then, we will process this stack. Pop each element from the stack, and go to the right side of that element.

Below is the source code for this version.

public List<Integer> inorderTraversal(TreeNode root) {
    List<Integer> res = new ArrayList<>();
    Stack<TreeNode> stk = new Stack<>();
    TreeNode tmp = root;
    boolean isContinue = true;

    do {
        // get the left side
        while (tmp != null) {
            stk.push(tmp);
            tmp = tmp.left;
        }

        // goes with right side
        if (stk.size() > 0) {
            tmp = stk.pop();
            res.add(tmp.val);

            tmp = tmp.right;
            isContinue = true;
        } else {
            isContinue = false;
        }
    } while (isContinue);

    return res;
}


Wrapping up

  • Understanding about the way of the inorder traversal in binary tree.