# Binary Tree Inorder Traversal

ID: 94; easy

## Solution 1 (Go)

``````/**
* Definition for a binary tree node.
* type TreeNode struct {
*     Val int
*     Left *TreeNode
*     Right *TreeNode
* }
*/
func inorderTraversal(root *TreeNode) []int {
result := make([]int, 0)
inorderHelper(root, &result)
return result
}

func inorderHelper(root *TreeNode, res *[]int) {
if root != nil {
inorderHelper(root.Left, res)
*res = append(*res, root.Val)
inorderHelper(root.Right, res)
}
}``````

## Solution 2 (Java)

``````/**
* Definition of TreeNode:
* public class TreeNode {
*     public int val;
*     public TreeNode left, right;
*     public TreeNode(int val) {
*         this.val = val;
*         this.left = this.right = null;
*     }
* }
*/

public class Solution {
/**
* @param root: A Tree
* @return: Inorder in ArrayList which contains node values.
*/
public List<Integer> inorderTraversal(TreeNode root) {
List<Integer> result = new ArrayList<>();
if (root == null) return result;
inorderTraversalHelper(root, result);
return result;
}

private void inorderTraversalHelper(TreeNode root, List<Integer> result) {
if (root == null) return;
inorderTraversalHelper(root.left, result);
inorderTraversalHelper(root.right, result);
}
}``````

### Notes

• Recursion / Divide and conquer

## Solution 3 (Java)

``````/**
* Definition of TreeNode:
* public class TreeNode {
*     public int val;
*     public TreeNode left, right;
*     public TreeNode(int val) {
*         this.val = val;
*         this.left = this.right = null;
*     }
* }
*/

public class Solution {
/**
* @param root: A Tree
* @return: Inorder in ArrayList which contains node values.
*/
public List<Integer> inorderTraversal(TreeNode root) {
List<Integer> result = new ArrayList<>();
Deque<TreeNode> stack = new ArrayDeque<>();
TreeNode curr = root;

while (curr != null || !stack.isEmpty()) {
while (curr != null) {
stack.push(curr);
curr = curr.left;
}
curr = stack.pop();