Introduction
It is my time to work on the binary search tree inorder successor. This time I had a better presentation.
My analysis and code
Here is the gist I created for my mock interview.
Analysis of the algorithm
After I have practiced the algorithm over 10 times, I start to come out new script for my analysis. I talked in the following this time and it was very welcomed by the peer with over 10 years experience in top 10 software companies.
I like to traversal the tree and then it is very easy to find the successor through the array. The access of the array takes O(1), but the traversal takes O(N) time since it is inorder traversal.
One way to beat the time complexity is to look up from the given node, either going down to the leaf node or going up to the root node. The maximum height of tree is the time complexity which is O(logn) in average.
No comments:
Post a Comment