Two Inorder Traversal Solutions (Using Recursion and Stack)


  • 0
    P

    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);
            list.add(root.val);
            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();
                    list.add(curr.val);
                    curr = curr.right;
                    i++;
                }
            }
            return list.get(k-1);
        }
    }
    

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


  • 0
    C

    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.


Log in to reply
 

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