# Binary Tree Inorder Traversal | Leetcode #94 | Medium

In this post I will discuss the solution to the leetcode problem — Binary Tree Inorder Traversal.

## Problem:

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

Example 1:

`Input: root = [1,null,2,3]Output: [1,3,2]`

Example 2:

`Input: root = []Output: []`

Example 3:

`Input: root = Output: `

Example 4:

`Input: root = [1,2]Output: [2,1]`

Example 5:

`Input: root = [1,null,2]Output: [1,2]`

Constraints:

• The number of nodes in the tree is in the range `[0, 100]`.
• `-100 <= Node.val <= 100`

Recursive solution is trivial, could you do it iteratively?

## Solution:

Trees are not linear data structures like arrays, lists etc. and hence they can be traversed in multiple ways. In-order traversal is a way of traversal where we visit the tree nodes in this order — left, root, right.

As the problem statement mentions, the recursive solution is trivial and asks to solve it in iterative way. Let’s solve them in both the ways.

1. Recursive Solution:

The structure of `TreeNode` is mentioned in the comments where it has `val` holding the value and `left` and `right` which are corresponding left and right child nodes.

Here is how the recursive algorithm looks like —

1. Create a `List<Integer>` and let’s call it `output` which will hold the result of in-order traversal.
2. Create a helper function `traverse()` which we can call recursively by passing a `TreeNode` .
3. Start by calling the `traverse()` function with `root` as the input.
4. As every recursive function needs a base condition so that the execution stops, in this case we check if the passed `root` is null or not. If it is, then we return an empty list.
5. Otherwise, call the `traverse()` function with `root.left` which will traverse the left subtree recursively.
6. Add `root.val` to the `output` which means we have visited the current node.
7. Call the `traverse()` function with `root.right` which will traverse the right subtree recursively.

That’s it. That traverses the entire tree in in-order way. Here is how the code looks like —

`/** * Definition for a binary tree node. * public class TreeNode { *     int val; *     TreeNode left; *     TreeNode right; *     TreeNode() {} *     TreeNode(int val) { this.val = val; } *     TreeNode(int val, TreeNode left, TreeNode right) { *         this.val = val; *         this.left = left; *         this.right = right; *     } * } */class Solution {    private List<Integer> output = new ArrayList();      public List<Integer> inorderTraversal(TreeNode root) {        return traverse(root);  }      private List<Integer> traverse(TreeNode root) {    if (root == null) {      return new ArrayList();    }        traverse(root.left);    output.add(root.val);    traverse(root.right);        return output;  }}`

2. Iterative Solution:

To traverse the tree in iterative way, we need to take help of another data structure i.e. Stack. As Stack is a last in first out (LIFO) data structure, it perfectly suits our needs to traverse the tree. Let’s see how —

1. Create a `List<Integer>` and let’s call it `output` which will hold the result of in-order traversal.
2. Create a stack for storing the `TreeNode` and call it `stack` .
3. Create a temporary TreeNode called `current` and initialized it with `root` .
4. Iterate the tree until the `current` is null OR the `stack` is empty.
5. As we are traversing in-order, we need to keep traversing left until we reach the leaf nodes i.e. the node does not have any children. We can do that by keep pushing the current nodes to the stack and moving current to the left.
6. Once we are done with step 5, we get the top most node from the stack i.e. `stack.pop()` which is our new `current` node.
7. Add it to the output.
8. Now we need to move to the right subtree and hence assign current to the left node.
9. Return the `output` .

This is how the code looks like —

`/** * Definition for a binary tree node. * public class TreeNode { *     int val; *     TreeNode left; *     TreeNode right; *     TreeNode() {} *     TreeNode(int val) { this.val = val; } *     TreeNode(int val, TreeNode left, TreeNode right) { *         this.val = val; *         this.left = left; *         this.right = right; *     } * } */class Solution {  public List<Integer> inorderTraversal(TreeNode root) {    List<Integer> output = new ArrayList();        Stack<TreeNode> stack = new Stack();        TreeNode current = root;            while(current != null || !stack.isEmpty()) {      while(current != null) {        stack.push(current);        current = current.left;      }            current = stack.pop();      output.add(current.val);      current = current.right;    }    return output;  }}`

I hope you enjoyed solving this problem and the solution helps! Happy coding! 🙂

If you think the solution can be improved or misses something, feel free to comment. There is always some room for improvement.

Find the solutions to the leetcode problems here — https://github.com/rishikeshdhokare/leetcode-problems

--

--

I am a Software Engineer from India and working in Berlin, Germany. I write about technology, my experiences in Germany, travel in Europe.