alchu8
BAN USERHow? Look at the exponential graph, it never goes below 0 past the x axis.
Also, 2^x = -4, give me x. You can't. The power of any positive integer, such as 2, is always positive. Remember that a number raised to a negative number is just a positive inverse. Therefore, this case is invalid.
Please confirm algorithm.
First find the lowest common ancestor of the 2 given nodes. Use the property of the BST that right child key > parent key > left child key. Since the root has a path to any node, start there.
If both keys are less than the root, go to the left subtree; if both keys are greater, go right. If the root key is between them, you've found the lowest common ancestor.
For going left/right, recursively iterate and repeat this comparison with your current node until you traverse to a node where its key is between the given 2 keys. Then as you recursively go back up the tree, return all parent nodes to give you back all common ancestors.
No extra space is used. Worst case is you traverse all the way down to the leaf level to find the lowest common ancestor. So time complexity is O(logn).
Simple algorithm, please confirm:
- alchu8 May 29, 20121. Start inserting elements from the end of the array into a BST.
2. As you're inserting current element, increment a counter when you go right, this will imply that current element is greater than parent.
3. Note that elements of left subtree of parent are less than parent and thus less than current element, so in addition to incrementing counter when going right, add all elements in the left subtree of that level.
4. If going left, increment a left_subtree_counter and keep that value in the parent so it can be easily tracked.
5. Do this until you get to the level for the current element.
This is simply building a BST, which takes O(nlogn).
Space O(n).