tristan.uva
BAN USERIn theory, correct.
In practice, you wouldn't be only hitting the algorithm just once in the entire life time of your program. But you only need to create the lookup table just once.
OK. Then I guess my definition of right edge is different from what the interviewer was expecting. It would be nice to clear up during interview...
But I am curious, if this is the case, then what is the difference between the solution for complete tree and regular tree?
This would work for complete binary tree, and most of incomplete binary trees, but not all of them.
Consider the following case, (I'm using the standard array representation of tree, for a[i], its left child is a[2i+1], its right child is a[2i+2]).
a tree: {0, 1, null, 2, 3, null, null, 4, 5, 6, 7, null, null, null, null}
0
1 n/a
2 3 n/a n/a
4 5 6 7 n/a n/a n/a n/a
this edge 1-3-7 is actually the right edge of the tree. The algorithm above would miss 3.
does the input contains duplicate strings?
- tristan.uva August 31, 2010consider an array 10, 4, 7. What would you do after you run compare(10, 4), which removes 4? Instead of running comparison between 10 and 4, you should keep advancing until you see a value larger than 10.
- tristan.uva August 27, 2010
Bottom-up. One of the key observation is: this is a BST, therefore if root.left.value==root.value(assume it is v), the entire sub-tree starting from root.left.right can be completely removed, because for any node n in that subtree, n.value would have to be equal to v because in that sub-tree, the following conditions would be true at the same time:
1. root.left.value <= n.value <= root.value,
2. root.left.value == root.value.
The same for root.right.left.
- tristan.uva April 02, 2011