O(n) using in-order traversal


  • 0
    M

    Probably not the best solution, but the concept is very easy. Traverse the BST in-order and keep count of the number of nodes visited. If equals to k, store the number and then return.

    The problem of this algorithm is that the traverse function is executed N times, so it is always O(N).
    Am wondering if anyone else has a better solution?

    public class Solution {
        
        private boolean found = false;
        private int k = 0;
        private int l = 0;
        private int val = Integer.MIN_VALUE;
        
        public int kthSmallest(TreeNode root, int k) {
            this.k = k;
            traverse(root);
            return val;
        }
        
        private void traverse(TreeNode node){
            if(found){
                return;
            }
            
            if(node.left != null){
                traverse(node.left);
            }
            
            l++;
            if(l == k){
                val = node.val;
                found = true;
            }
            
            if(node.right != null){
                traverse(node.right);
            }
        }
    }

Log in to reply
 

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