Solution


How to traverse the tree

There are two general strategies to traverse a tree:

  • Depth First Search (DFS)

    In this strategy, we adopt the depth as the priority, so that one would start from a root and reach all the way down to certain leaf, and then back to root to reach another branch.

    The DFS strategy can further be distinguished as preorder, inorder, and postorder depending on the relative order among the root node, left node and right node.

  • Breadth First Search (BFS)

    We scan through the tree level by level, following the order of height, from top to bottom. The nodes on higher level would be visited before the ones with lower levels.

On the following figure the nodes are numerated in the order you visit them, please follow 1-2-3-4-5 to compare different strategies.

postorder

To solve the problem, one could use the property of BST : inorder traversal of BST is an array sorted in the ascending order.




Approach 1: Recursion

It's a very straightforward approach with time complexity. The idea is to build an inorder traversal of BST which is an array sorted in the ascending order. Now the answer is the k - 1th element of this array.

bla

Complexity Analysis

  • Time complexity : to build a traversal.
  • Space complexity : to keep an inorder traversal.


Approach 2: Iteration

The above recursion could be converted into iteration, with the help of stack. This way one could speed up the solution because there is no need to build the entire inorder traversal, and one could stop after the kth element.

bla

Complexity Analysis

  • Time complexity : , where is a tree height. This complexity is defined by the stack, which contains at least elements, since before starting to pop out one has to go down to a leaf. This results in for the balanced tree and for completely unbalanced tree with all the nodes in the left subtree.
  • Space complexity : , the same as for time complexity, in the worst case, and in the average case.


Follow up

What if the BST is modified (insert/delete operations) often and you need to find the kth smallest frequently? How would you optimize the kthSmallest routine?

Insert and delete in a BST were discussed last week, the time complexity of these operations is , where is a height of binary tree, and for the balanced tree.

Hence without any optimisation insert/delete + search of kth element has complexity. How to optimise that?

That's a design question, basically we're asked to implement a structure which contains a BST inside and optimises the following operations :

  • Insert

  • Delete

  • Find kth smallest

Seems like a database description, isn't it? Let's use here the same logic as for LRU cache design, and combine an indexing structure (we could keep BST here) with a double linked list.

Such a structure would provide:

  • time for the insert and delete.

  • for the search of kth smallest.

bla

The overall time complexity for insert/delete + search of kth smallest is instead of .

Complexity Analysis

  • Time complexity for insert/delete + search of kth smallest: , where is a tree height. in the average case, in the worst case.

  • Space complexity : to keep the linked list.

Analysis written by @liaison and @andvary