Leetcode — 94. Binary Tree Inorder Traversal

The link to the problem: https://leetcode.com/problems/binary-tree-inorder-traversal/

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

For example, when input is [1,2,3,4,5,null,7] (like the graph below)
Output should be [4,2,5,1,3,7]

root = [1,2,3,4,5,null,7]

Thoughts:

It is not hard to solve this problem recursively as long as you know what inorder means.

Inorder is one of the types of tree traversal. We will always first traverse its left node, the node itself, then its right node. Hence, if we inorder traverse a binary search tree, we will get a sorted list.

Hence it won’t be too hard to come up with this solution -

public List<Integer> inorderTraversal(TreeNode root) {
        List<Integer> list = new ArrayList<>();
        helper(list,root);
        return list;
    }
    public void helper(List<Integer> list, TreeNode node){
        if(node==null)
            return;
        helper(list,node.left);
        list.add(node.val);
        helper(list,node.right);
    }

However, this will not be enough during an interview. If this is your interview question, it is a high possibility that the interviewer will ask you how do you do it iteratively.

Since we cannot do it recursively, we definitely need “something” to store the nodes. Hmm, so here comes the question, which data structure should we choose, queue or stack? 😕

If we use a queue (First In First Out), we will always get the node that we put in at the very beginning. However, if we use a stack (Last In First Out), we will get the node that we just put in.

💭 That is to say, in this inorder traversal situation, since we want to get the leftmost node, it is better to use the stack to solve this problem.

We have three variables —

1. node for recording the current node we want to traverse. We will use a loop to traverse the node from the node itself to its leftmost node.
2. stack for storing the nodes that are waiting to be extracted next. We will place the top node of the stack into the list.
3. list for recording the inorder result.

We will stop the loop when node is null AND stack is empty.

✏️In stack, we actually store a TreeNode instead of “a single node”. However, since the size of TreeNode will be too big to fit in stack, I will just put the “root of the TreeNode” in the stack.

You can think of we will always first traverse the node and its left nodes and store them into stack. Then you might wonder what about the right nodes? 😟
We will always traverse the node’s right node by assigning node’s right to node after placing node’s value to the list. (See the below steps to understand thoroughly)

🔧Step 1. Initial State. list and stack are empty; node is the root of the tree.

initial state

🔧Step 2. Place all the left nodes of the current node into stack. node is now null since we keep assigning node to its left node after placing the current node into stack.

step 2 result

🔧Step 3. We put the top node’s value (i.e., 4) into list. Now, let node be the top node’s right node, which is null in this round.

step 3 result

🔧Step 4. Place all the left nodes of the current node into stack - no nodes will be added to stack in this round because the current node is null. We put the top node’s value (i.e., 2) into list. Let node be the top node’s right node, which is 5. (see the top left of the graph to see the structure of node 2)

step 4 result

🔧Step 5. Place all the left nodes of the current node into stack — only 5 will be added to stack this time since 5 doesn’t have any left nodes. We put the top node’s value (i.e., 5) into list. Let node be the top node’s right node, which is null.

step 5 result

🔧Step 6. Place all the left nodes of the current node into stack — no nodes will be added to stack in this round because the current node is null. We put the top node’s value (i.e., 1) into list. Let node be the top node’s right node, which is 3.

step 6 result

🔧Step 7. Place all the left nodes of the current node into stack —only 3 will be added to stack this time since 3 doesn’t have any left nodes. We put the top node’s value (i.e., 3) into list. Let node be the top node’s right node, which is 7.

step 7 result

🔧Step 8. Place all the left nodes of the current node into stack — only 7will be added to stack this time since 7 doesn’t have any left nodes. We put the top node’s value (i.e., 7) into list. Let node be the top node’s right node, which is null.

step 8 result

🔧Step 9. Both node and stack are null and empty. There’s no node left to be added to the list. We’re done!

public List<Integer> inorderTraversal(TreeNode root) {
        List<Integer> list = new ArrayList<>();
        Stack<TreeNode> stack = new Stack<>();
        TreeNode node = root;
        while(node!=null || !stack.isEmpty())
        {
            while(node!=null)
            {
                stack.push(node);
                node = node.left;
            }
            list.add(stack.peek().val); //take the top node value
            node = stack.pop().right; //node be the right node
        }
        return list;
    }

Both the recursive solution and iterative solution are 0ms code that beat 100%.