How to traverse the tree
There are two general strategies to traverse a tree:
Depth First Search (
In this strategy, we adopt the
depthas 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
postorderdepending on the relative order among the root node, left node and right node.
Breadth First Search (
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,
1-2-3-4-5 to compare different strategies.
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
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.
- 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.
- 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.
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?
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 :
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.
The overall time complexity for insert/delete + search of kth smallest is instead of .
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.