Problem Statement:
Given the root of a binary tree, return the inorder traversal of its nodes’ values..
Examples:
Example 1:
Input: root = [1,null,2,3]
Output: [1,3,2]
Explanation:
Example 2:
Input: root = [1,2,3,4,5,null,8,null,null,6,7,9]
Output: [4,2,6,5,7,1,3,9,8]
Explanation:
Example 3:
Input: root = []
Output: []
Example 4:
Input: root = [1]
Output: [1]
Constraints:
- The number of nodes in the tree is in the range
[0, 100]. -100 <= Node.val <= 100
Approach
- Use recursion to traverse the binary tree in inorder way:
- First, visit the left subtree.
- Then,
add the current node’svalue. - Finally, visit the right
subtree. - Store the result in an array and return it.
Time Complexity:
Time Complexity = O(n)
Space Complexity:
Space Complexity = O(n)
Dry Run
Input: root = [1, 2, 3, null, 4]
Tree Structure:
1
/ \
2 3
\
4
Initialize:
ans = []
Start traversal(root = 1)
→ curr = 1
→ traversal(curr.left = 2)
→ curr = 2
→ traversal(curr.left = null) → return
→ ans.push(2) → ans = [2]
→ traversal(curr.right = 4)
→ curr = 4
→ traversal(curr.left = null) → return
→ ans.push(4) → ans = [2, 4]
→ traversal(curr.right = null) → return
← return to curr = 2 → done
← return to curr = 1
→ ans.push(1) → ans = [2, 4, 1]
→ traversal(curr.right = 3)
→ curr = 3
→ traversal(curr.left = null) → return
→ ans.push(3) → ans = [2, 4, 1, 3]
→ traversal(curr.right = null) → return
← return to curr = 1 → done
Traversal complete.
Final ans = [2, 4, 1, 3]
Output: Result: [2, 4, 1, 3]
var inorderTraversal = function(root) {
let ans = [];
function traversal(curr){
if(!curr) return;
traversal(curr.left);
ans.push(curr.val);
traversal(curr.right);
}
traversal(root);
return ans;
};
def inorderTraversal(root):
ans = []
def traversal(curr):
if not curr:
return
traversal(curr.left)
ans.append(curr.val)
traversal(curr.right)
traversal(root)
return ans
public List inorderTraversal(TreeNode root) {
List ans = new ArrayList<>();
void traversal(TreeNode curr) {
if (curr == null) return;
traversal(curr.left);
ans.add(curr.val);
traversal(curr.right);
}
traversal(root);
return ans;
}
vector inorderTraversal(TreeNode* root) {
vector ans;
function traversal = [&](TreeNode* curr) {
if (!curr) return;
traversal(curr->left);
ans.push_back(curr->val);
traversal(curr->right);
};
traversal(root);
return ans;
}
void traversal(struct TreeNode* curr, int* ans, int* index) {
if (!curr) return;
traversal(curr->left, ans, index);
ans[(*index)++] = curr->val;
traversal(curr->right, ans, index);
}
int* inorderTraversal(struct TreeNode* root, int* returnSize) {
int* ans = malloc(1000 * sizeof(int)); // assume max 1000 nodes
*returnSize = 0;
traversal(root, ans, returnSize);
return ans;
}
public IList InorderTraversal(TreeNode root) {
List ans = new List();
void Traversal(TreeNode curr) {
if (curr == null) return;
Traversal(curr.left);
ans.Add(curr.val);
Traversal(curr.right);
}
Traversal(root);
return ans;
}
