[Java] Find k-th smallest element in BST

We saw how to find the second biggest element in a BST, now let's invert the search and look for the k-th smallest element instead.

We could do this operation in O(N) time by doing a preorder traversal of the tree and counting the elements visited so far, but this would not be taking advantage of the BST property. Since we know that, we can instead extend the Node definition to add a new value: leftSize. Each node now tracks the number of items in its left subtree, therefore allowing us to take advantage of the BST property while searching for the K-th smallest element.

The idea is as follows:

• the smallest element is K = 1 and will definitely sit all the way on the left
• nodes that do not have a left subtree have a leftSize of 0
• an element is exactly in position K only when its leftSize + 1 = K

Now, to use the BST property we need to decide where to redirect the search in case the property above does not hold for the current node. Imagining the tree nodes listed sequentially we can easily figure out that:

• if K <= leftSize of the current node, then we need to walk down the left subtree of this node. There are many nodes smaller than the current one, therefore we should search there.
• otherwise we have to walk down the right subtree of this node BUT we also need to adjust the value of K to K - 1 - leftSize of the current node before doing the recursive call on that subtree. This is because we know the current node (-1) and all the other nodes on the left subtree (-leftSize) can be discarded since they are in a position smaller than the requested K in the preorder traversal of the tree so we need to search in the remaining ones sitting on the right subtree. We basically convert the problem to finding the (K - already checked elements)-th smallest element in a new tree rooted at the first right child of the current node.

If none of the above conditions can be met, then K is bigger than the total tree size, therefore we should return null or throw an exception.

You can check my implementation of getKthSmallestElement on my Gist alongside some test cases in BSTJTests.

And bonus: Order statistic trees already implement this feature by design :)

[Java] Reverse words in char array

Given an array of characters representing a text with words separated by a single space, reverse the text. Eg:

{'c', 'a', 's', 'e', ' ', 't', 'e', 's', 't', ' ', 'm', 'y'}

should read "my test case" in output.

This can be done in constant O(1) space by handling the array in place and in O(N) time.

The idea is to reverse the full array first, then find each word (they are delimited by a space) and reverse them in place again. So:

{'c', 'a', 's', 'e', ' ', 't', 'e', 's', 't', ' ', 'm', 'y'}

becomes

{'y', 'm', ' ', 't', 's ', 'e', 't', ' ', 'e', 's', 'a', 'c'}

and finally

{'m', 'y', ' ', 't', 'e', 's', 't', ' ', 'c', 'a', 's', 'e'}

The key point is to track where did we arrive with each word reversal so that we actually keep the runtime linear, I would say it is exactly 3N, once for reversing the full array, once for scanning the array while finding the delimiters and once for reversing each word starting and ending at the marked indexes.

You can check my implementation of reverseWords on my Gist alongside some test cases in ReverseWordsJTests.

[Java] Find second largest element in BST

Easy question: given a BST, find the second largest element in there.

This can be done in many ways, the most efficient one uses constant O(1) space and O(N) worst case time (tree is unbalanced).

The idea is to walk the tree until we find the biggest element (the one all the way to the right), then check if that node has children. If not, then the second biggest must be his parent; if yes, then the second biggest node is in the left subtree, all the way to the right there. If no right node exists, then it is the left children of the biggest node we found.

My implementation uses the parent pointers, but this can be done all the same without it, by simply tracking an additional node during the looping.

You can check my implementation of getSecondBiggestElement on my Gist along with some test cases in BSTJTests.