# Binary Tree Inorder Traversal

Published: Sep 30, 2022

Easy Depth-First Search Binary Tree

## Problem Description

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

Constraints:

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

https://leetcode.com/problems/binary-tree-inorder-traversal/

## Examples

``````Example 1
Input: root = [1,null,2,3]
Output: [1,3,2]
Explanation:
1
\
2
/
3
``````
``````Example 2
Input: root = []
Output: []
``````
``````Example 3
Input: root = [1]
Output: [1]
``````

## How to Solve

This is a basic inorder traversal problem. Just visit all nodes in the binary tree following the inorder manner.

The tree traversal here takes the depth-first search (DFS) style. The traverse function does the DFS and saves values between going left and right nodes.

## Solution

``````#include <vector>

using namespace std;

struct TreeNode {
int val;
TreeNode *left;
TreeNode *right;
TreeNode() : val(0), left(nullptr), right(nullptr) {}
TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}
};

class BinaryTreeInorderTraversal {
private:
vector<int> traverse(vector<int> &values, TreeNode *root)
{
if (root)
{
values = traverse(values, root->left);
values.push_back(root->val);
values = traverse(values, root->right);
}
return values;
}
public:
vector<int> inorderTraversal(TreeNode* root) {
vector<int> values;
return traverse(values, root);
}
};
``````
``````/**
* 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 BinaryTreeInorderTraversal {
private List<Integer> traverse(List<Integer> values, TreeNode root) {
if (root == null) { return values; }
traverse(values, root.left);
traverse(values, root.right);
return values;
}
public List<Integer> inorderTraversal(TreeNode root) {
List<Integer> values = new ArrayList<Integer>();
return traverse(values, root);
}
}
``````
``````function TreeNode(val, left, right) {
this.val = (val===undefined ? 0 : val)
this.left = (left===undefined ? null : left)
this.right = (right===undefined ? null : right)
}

/**
* @param {TreeNode} root
* @return {number[]}
*/
var inorderTraversal = function(root) {
const traverse = function(values, root) {
if (root === null) { return values; }
values = traverse(values, root.left);
values.push(root.val);
values = traverse(values, root.right);
return values
}
return traverse([], root);
};

``````
``````# Definition for a binary tree node.
# class TreeNode:
#     def __init__(self, val=0, left=None, right=None):
#         self.val = val
#         self.left = left
#         self.right = right

from typing import Optional

class BinaryTreeInorderTraversal:
def inorderTraversal(self, root: Optional[TreeNode]) -> List[int]:
def traverse(result, root):
if not root:
return result
result = traverse(result, root.left)
result.append(root.val)
result = traverse(result, root.right)
return result
return traverse([], root)
``````
``````# Definition for a binary tree node.
# class TreeNode
#     attr_accessor :val, :left, :right
#     def initialize(val = 0, left = nil, right = nil)
#         @val = val
#         @left = left
#         @right = right
#     end
# end
# @param {TreeNode} root
# @return {Integer[]}
def traverse(values, root)
if !root
return values
end
traverse(values, root.left)
values << root.val
traverse(values, root.right)
values
end

def inorder_traversal(root)
traverse([], root)
end
``````

## Complexities

• Time: `O(n)`
• Space: `O(n)`