Java in order traversal in 0 ms beating 95%


  • 2
    Z
    public class Solution {
        private int counter;
    
        private TreeNode kthSmallestNode(TreeNode root, int k) {
            if (root == null) return null;
            TreeNode left = kthSmallestNode(root.left, k);
            if (left != null) return left;
            if (++counter == k) return root;
            return kthSmallestNode(root.right, k);
        }
    
        public int kthSmallest(TreeNode root, int k) {
            counter = 0;
            return kthSmallestNode(root, k).val;
        }
    }

  • 0
    E

    Do you mind providing some explanation of your code? Thanks.


  • 0
    T

    He has a global counter that increments by one every time he visits a node. He defines visiting a node when he finished looking at the left subtree and is now looking at the root. When the root is the nth node he visited, it is by default the nth smallest node. This is because he is doing an inorder traversal on a bst.

    private TreeNode kthSmallestNode(TreeNode root, int k) {
        if (root == null) return null; // if the root is null, no where else to go there is no answer, return null
        TreeNode left = kthSmallestNode(root.left, k); // traverse all the left sub tree
        if (left != null) return left; // if the left was not null, that means the line below must have ran on some stack, the non null node we'll be getting must be the answer. If it is null, that means the counter never == k,  that means there wasnt enough values in the left subtree.
        if (++counter == k) return root; //if counter==k, we visited k nodes, by bst and in order traversal return root (the answer)
        return kthSmallestNode(root.right, k); // if root is not it, and left is not it, return what ever we find in right, it might be null or it might be the correct node. Again if it returns null, that means the entire right tree + left tree did not have enough nodes to be == k
    }
    

  • 0
    F

    Thanks @tom47 for adding clear explanation.


Log in to reply
 

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