# Two Inorder Traversal Solutions (Using Recursion and Stack)

• Recursion:

``````public class Solution {
public int kthSmallest(TreeNode root, int k) {
List<Integer> res = new ArrayList<>();
inorderTraversal(res, root);
return res.get(k-1);
}

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

Stack:

``````public class Solution {
public int kthSmallest(TreeNode root, int k) {
Stack<TreeNode> stack = new Stack<>();
List<Integer> list = new ArrayList<>();
int i = 0;
TreeNode curr = root;
while (!stack.empty() || curr != null || i < k) {
if (curr != null) {
stack.push(curr);
curr = curr.left;
} else {
curr = stack.pop();
curr = curr.right;
i++;
}
}
return list.get(k-1);
}
}
``````

I am curious about why recursive solution is much faster than stack? (3ms and 12ms)

• In the iterative solution, the overhead of all the list operations can be avoided, you just don't have to maintain a list. Decrease k's value whenever you pop a node from the stack. You return the value of the node when k == 0.

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.