# Binary Tree Inorder Traversal LeetCode Solution

Difficulty Level Easy
Binary Tree Depth First Search Stack TreeViews 141

## Problem Statement:

Binary Tree Inorder Traversal LeetCode solution

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]
```

### Input:

``` root = []
```

``` []
```

### Input:

``` root = [1]
```

``` [1]
```

### Constraints:

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

## Approach:

1. We will do recursion to find the binary tree inorder traversal. of a tree.

2. In order traversal means first to traverse the left subtree, then the root of the tree, at last, the right subtree (left->root->right).

3. The Base condition of our recursion will be when we reach the leaf node i.e. root will be null.

4. Finally, we’ll be left with binary tree inorder traversal.

## Code:

### Binary Tree Inorder Traversal C++ solution:

```class Solution {
public:
#define ll int

void rec(TreeNode *root,vector<ll>&v)
{
if(root==NULL)
return;
rec(root->left,v);
v.push_back(root->val);
rec(root->right,v);
}
vector<int> inorderTraversal(TreeNode* root) {
vector<ll>v;
rec(root,v);
return v;
}
};```

### Binary Tree Inorder Traversal Java solution:

```class Solution {
void rec(TreeNode root,List<Integer> ans)
{
if(root==null)
return;
rec(root.left,ans);
rec(root.right,ans);
}
public List<Integer> inorderTraversal(TreeNode root) {
List<Integer>ans= new ArrayList<>();
rec(root,ans);
return ans;
}
}```

## Time Complexity:

Time complexity will be o(n). We are traveling every node only once.

## Space Complexity:

Space complexity will be o(n). We are storing the value of every node for our traversal that’s why we are taking space of o(n).

Translate »