buckCherry
BAN USERwhat is s in the last line?
- buckCherry May 13, 2009x>>1 => x/2 only when x is power of 2.
Example:
if x=3(in decimal)=0011(in binary)
then x>>1 = 0001(in binary) =1(decimal)
do u think 3.5x=3.5*3 is same as (3>>1)+3+(3<<1)
Only if two arrays contain keys in exactly same order then binary trees (or even binary search tree) formed from them will be identical.
You might think fixing root node might be sufficient condition but its not as well.
Example: Array A contains : 1,2,3,4 and Array B contains: 1,3,2,4
Binary Tree from Array A taking elements from left to right is:
1
/ \
2 3
/
4
Binary Search Tree from Array B taking elements from left to right is:
1
/ \
3 2
/
4
Binary Search Tree from Array A taking elements from left to right is:
1
\
2
\
3
\
4
Binary Search Tree from Array B taking elements from left to right is:
1
\
3
/\
2 4
As you can see these two trees are not identical because the keys in the arrays are not in same order. Even in this case first element being same (which is another way of saying that same root for both trees) the trees are not identical because rest of the keys after root are not in same order in the arrays.
I guess even if we want to build balanced search tree with same algorithm (like red-black or AVL tree) the necessary condition will be the same as binary tree.
Here is a solution (algorithm) which uses additional memory complexity O(1) and run-time O(n).
----------------------------------------------------------------------------------------------------------------------------
- buckCherry June 28, 2012