# Binary Tree | Inorder Traversal

Gowthaman Ravi
·Jan 26, 2022·

Subscribe to my newsletter and never miss my upcoming articles

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 = [1] Output: [1]

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

Java Solution

``````**Approach: Morris Traversal**

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> res = new ArrayList<>();
TreeNode curr = root;
TreeNode pre;
while (curr != null) {
if (curr.left == null) {
curr = curr.right; // move to next right node
} else { // has a left subtree
pre = curr.left;
while (pre.right != null) { // find rightmost
pre = pre.right;
}
pre.right = curr; // put cur after the pre node
TreeNode temp = curr; // store cur node
curr = curr.left; // move cur to the top of the new tree
temp.left = null; // original cur left be null, avoid infinite loops
}
}
return res;
}
}
``````

C++ Solution

``````  Definition for a binary tree node.
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 Solution {
public:
vector<int> inorderTraversal(TreeNode* root) {
stack<TreeNode*> s;
vector<int> res;
TreeNode * node=root;
while(!s.empty() || node!=NULL){
while(node!=NULL){
s.push(node);
node=node->left;
}
node= s.top();
s.pop();
res.push_back(node->val);
node=node->right;
}
return res;
}
};
``````