buckCherry
BAN USER@yinyan - In java, the memory management is automatic (i.e. JVM is responsible for it and not the application developers). So you're idea of removing only the reference of the root of the tree would eventually free all the memory. However, for the sake of understanding this question, the java-equivalent would be: How could you remove all the parent child references in a binary-tree without recursive algorithm!
- buckCherry January 30, 2013One vote down, since this solution is not generic enough!
- buckCherry January 02, 2013Richard - I think u got it right. One vote up to you.
- buckCherry December 09, 2012Being polite I could say this answer is half way to the correct one.
For example fly v= 90, Train V=30, Tunnel L=16 leaves the fly's position 90x16/2x30 = 24 which is wrong since the particle is vibrating within 16 unit tunnel.
See Richard's solution in this post and I think he got it right for us.
One vote down from me to this answer.
To everyone:
I believe if you want to do well in probability then just explaining your answer is not enough, you should also learn to explain why other's answer is different from yours and may be why other's answer is wrong.
To Anonymous:
The way you've thought and got an answer 1/10 is not incorrect but there are few subtleties that you should understand.
In a circular table how we decide various arrangement of n people depends on how you model the case. There are two general approaches - (1) One way is to consider based on who is at one's left or right and if that differs then we call it's a different arrangement,. In this case we implicitly consider all chairs/seats are equivalent. (2)The other way to call two arrangements different is even when same people are to each other's left and right but they now occupy a different seats. In this case seats are implicitly not equivalent - may be seats are numbered or colored etc.
Every one solved this question with answer 1/2 implicitly assumed 1st case of equivalent chairs/seats. Since you've assumed probability that A sits in one of the 5 seats = 1/5, I could guess that you've implicitly taking 2nd approach where chairs also got numbering (or some kind of identifications).
Important thing to note here is that even with this numbered chairs P(A takes any one of the numbered seat) = 1 and not 1/5. This is because sample space of this experiment = sample space of the event = {C1, C2, C3, C4, C5} where C1= A takes chair 1 and so on.
To match up the answer 1/5, the event should be A takes a specific seat say C1.
Thus P(A takes C1)= 1/5
Now for this specific seating by A, B got 4 options {C2,C3,C4,C5} and the sample space for the event that B seats next to A is {C2, C5}. Thus for this specific seating of A at C1, the probability that B seats next to A=2/4 (technically this is a conditional probability).
So the answer you got i.e. 0.1 matches to a question something like – what’s the probability that A sits to a specific chair and B sits next to it!
Now I guess the missing link between the approach 1 where the answer is 1/2 and the approach 2 where your answer was 1/10 is that even when you considered the chairs are different, you didn’t answer the original question – what’s the probability that A and B seat next to each other. You didn’t consider all the cases that A can sit in C2, C3 etc.
Thus using 2nd approach the correct probability is P(A takes C1 and B sits next to A) + P(A takes C2 and B sits next to A)+... = (1/10)+ (1/10) + up to 5 times = 1/2.
Now you could see that either way correct answer is 1/2.
Even though you're answer expressed as a range is correct, there exists an exact value. So one vote down from me so that readers get to know more precise answer on this.
- buckCherry November 21, 2012First of all, its a wrong answer. The correct exact answer is 9/10. See my post below.
Secondly, language is not clear enough to understand what you're trying to say. Still here is how I would solve using your approach.
If all balls which are taken out are white in color.. then probability of 101st ball being black becomes 900/900=1
and if all the balls which are taken out are black in color.. then probability of 101st ball being black becomes
800/900
.89
so probability that 101st ball will be black should lie between 1 and .89
How ever here we can calculate exact value of the probability which is 0.9 and it conforms to the fact that it lies between [0.89 , 1.00]
One vote down from me
I always believe that if a probability question can be solved with various approaches, it makes the understanding more clear.
In that vain I've listed below couple of solutions :
1)Intuitively such probability questions often yields answer similar to avg case. Thus we can assume that 9:1 ratio of black to white balls will be maintained when 100 balls are drawn leaving 900 - 90 = 810 black balls and 100-10=90 white balls.
Thus probability of picking a black ball from a population of 900 balls with distribution (810 B + 90 W) is 810/900
=9/10.
Now one thing that can haunt you is that we're calculating this probability in a modified sample space with 900 balls after executing a conditional event of picking 100 balls without returning. So will the probability of this the given event will be same in the context of original sample space of 1000 balls! We can intuitively argue that since the probability of the conditioning event is 1 (probability of removing 100 balls from 1000 balls is 1), most likely the probability of the event in both the sample space (i.e. both conditional and unconditional probabilities) will be same.
2)Mathematically we can calculate the final probability as below.
Method 1:
Let's define two events X and Y in the original sample space of 1000 balls where
X=The event of picking 100 balls at random and discarding
Y=The composite event of picking 100 balls and discarding followed by picking another ball and noting its color
The desired question is P(Y=black) = (no. of outcomes for Y=black) / (no. of outcomes for Y=any color)
= (900P1x999P100)/ 1000P101 [Note uPv implies permutation of v elements from u distinct elements]
= 9/10
Method 2:
The experiment can be equivalent to arranging 1000 elements such the left most 100 elements will be first 100 elements to be discarded and color of the 101st element from left will be observed.
Thus desired probability = number arrangements with 101st left most element is black / number of arrangement of 1000 elements
= 900P1 x (999!) / (1000!)
= 900/1000
One vote down since it doesn't seem to work and the author didn't explain it enough to clarify all the doubts!
- buckCherry November 21, 2012One vote down since it doesn't seem to work and the author didn't explain it enough to clarify all the doubts!
- buckCherry November 21, 2012With same time complexity of O(n) but will less visit, we can solve this.
Traverse once and if you encounter 1, keep the node and if otherwise move them to corresponding list identified by two pointers 2nd & 3rd. We also need another pointer to keep track of tail of the list holding 2's (i.e. the one having 2nd pointer as head). Now when you finish traversing and separating 2's and 3;s from the list, all you need to do is point last element of original node to the list with 2's and point the tail of this list to the start of the list with 3's.
I'll write down three cases and to me I couldn't find out what algorithm I should use for counting so that sum of the two counts becomes the answer.
1) A->B->C->D->C
algo line #2: they meet at C
algo line #3: The path tortoise make is A-B-C
Considering we count number of nodes we get 3
algo line #4: The path tortoise make is A-B-C (The hare's path
is C-D-C)
Considering the node excluding start and end of
tortoise's move we get count 1
Note your algorithm says .."meanwhile keep
counting number of nodes" which doesn't fit here though!!
So by summing 3+1=4 we get our desired answer
Now let's verify these counting algorithm with two
more examples
2) A->B->C->D->E->D
#2: they meet at E (Tortoise: A-B-C-D-E and Hare: A-C-E-E-E)
#3: The path tortoise make is A-B-C-D-E
Considering we count number of nodes we get 5
#4: The path tortoise make is A-B-C-D (The hare's path
is E-D-E-D)
Considering the node excluding start and end of tortoise's
move we get count 2
So by summing 5+2=7 we get a wrong answer
3) A->B->C->A
#2: they meet at A (Tortoise: A-B-C-A and Hare: A-C-B-A)
#3: The path tortoise make is A-B-C-A (even thoug your algo is
unclear here and alternate path could be A )
Considering we count number of nodes we get 4 (or
alternately 1)
#4: The path tortoise make is A-B (alternately A)
Considering the node excluding start and end of tortoise's
move we get count 0
So by summing 4+0=4 (alternately 1+0=1) we get wrong
answers in both ways
manjunath426jc:
The difference between the recursive solution by 'crdmp' and the 2nd approach of 'Victor' is that in recursive solution, the system(language-library and/or OS) will maintain a stack where as in 'Victor' case the program will explicitly maintain a stack.
To me none of them are reversing the list and using explicit stack is always better than a recursive solution since system's method stack consumes more memory and cause performance overhead than explicit stack maintenance.
In fact my vote goes to Victor's 2nd approach.
shodnik:
Thanks for taking time to explain all my doubts. It helps big time.
couple of concerns though:
1) The line#4 of your algo says that tortoise is set to head while hare is fixed. So #4 should start with tortoise=Head and hare=C and with this if they move a step each time then they never meets. I didn't get why you've started your line#4 setting tortoise to A which is first element of the list and not the head!!
2)Even if you change your algorithm to indicate that in line#4 tortoise should start from first element then we get a count 4 when both of them meet at D as you've explain on Nov 17th's post. However your algorithm says 'Find sum of the counts if hare was not at NULL' and based on this the answer your algo yields is 3+4=7 which is obviously wrong!!
shodnik:
If 3 elements/nodes were mandatory for a loop/cycle then the term 'self-loop' would have never existed!!!
I can neither agree with your requirement of at least 3 nodes for a cycle nor could understand why you're calling the above example's linked-list as partial doubly linked list.
Here is my versions of definitions and would love to see your version of the definitions.
Cycle/Loop: In a generic sense a cyclic path or loop is a path where starting from a point if you keep moving in same direction, you come back to the same point. Extending the same idea, in a linked-list if there exists any node where we can come back again by moving in one direction from that node, we call the linked list to have a loop/cycle. This definition doesn't mandate any node requirements. And using this definition, the example list Head->A->B->C->D->C is a linked list with cycle/loop since starting from C we can come back to C.
In addition, you might like to check cycle definitions in Graph theory as they are also CS data structure and we can expect certain similarity with linked-list.
Link: mathworld.wolfram.com/CycleGraph.html
Doubly Link list: If each node of a linked list stores two references - one for forward/next node and other for previous/backward node then it's a doubly linked list.
Since the example linked list I provided are neither capable of nor have stored two pointers per node they are not doubly linked list. Not sure why you call it 'PARTIAL' doubly linked list as not a single node in my example has two references.
Unfortunately, one vote down from me and am looking forward to your response
I'm surprised that none of you have mentioned how you'll move forward as well as backward of any arbitrarily given node!!
To me the catch is to assume that the list be either a doubly linked list or a circular list so that given any arbitrary node, you can traverse through all nodes.
Once any one of these assumptions is considered, rest of the solution is trivial.
maverick:
The concept of Diameter of a tree is derived from the concept of diameter of a graph in Graph Theory. The mathematical definition is
diameter of G = max ( d(u,v) ) for all u,v in G
G is a graph
u,v are any vertices in G
d(u,v) is the distance between u and v and is calculated based on number of edges in a path with two ends as u and v
Thus Graph theoretically diameter is calculated based on number of edges and not on the nodes.
Bibliography:
[1] mathworld.wolfram.com/GraphDiameter.html
[2] mathworld.wolfram.com/GraphDistance.html
[3] mathworld.wolfram.com/GraphEccentricity.html
[4] A Beginner's Guide to Graph Theory By W.D. Wallis. Chapter 2.2 Radius, Diameter and Eccentricity [worked out example. Available in google books.
books.google.co.in/books?id=mpPK7CWEQnkC&pg=PA23&source=gbs_toc_r&cad=4#v=onepage&q&f=false ]
Regarding your proposal for storing leafs and avoiding BFS's, it's official that I cannot solve it. Please show us how to do it!!
maverick:
1) How a height is defined can vary as long as you're not screwing up things. It's just a conceptual convention you would like to follow just like we follow different indexing for arrays. While one can consider height of leaf node=0 other can consider 1. In my case I've considered height of leaf node as 0.
2)With this definition of height I think the diameter definition/calculation is correct as well.
Example i: A tree with root A and A has two children B & C
h1=findMaxDepthAndUpdateResults(B,...) will return 0
similarly
h2=findMaxDepthAndUpdateResults(B,...) will return 0
Now diameter from B to C is 2 since number of edges in B-A-C is 2.
In my calculation dia=h1+1+h2+1=2 seems correct as per my definition of height.
Example ii: Root A has two children B & C and C has another right child D. Applying the algorithm you'll get
h1=findMaxDepthAndUpdateResults(B,...) will return 0
similarly
h2=findMaxDepthAndUpdateResults(C,...) will return 1
thus dia of A= h1+1+h2+1=0+1+1+1=3 which is in accordance with edges in the path B-A-C-D
Example iii: Root A has one child B
In such cases I've omitted calculating diameter since there doesn't exists at least two leaves to form a diameter
3) Finally, would you please. write some pseudo/concrete code on how the leaf can be stored avoiding the two BFS'!!
I guess it is good know about other algorithms besides Floyd's:
//Algorithm invented by Richard P. Brent and runs in O(n) time.
//Outline: initially rabbit and turtle starts
// off at same position however only rabbit moves by a step
// and checks if it meets the turtle. When it does
// not after a certain number of steps, the stationary
// turtle will be teleported to rabbit's position.
// The step counter as well as the limit of steps will
// will be reset. and rest of the actions just repeats.
//Algorithm starts here:
//assuming head would not point to head
//we start from 1st element, other wise
//we could have started from head as well
turtle = head ->next
rabbit = head ->next
steps_taken = 0
step_limit = 1 //1=2 power 0
forever:
if rabbit == end:
return 'No Loop Found'
end-if
rabbit = rabbit->next
steps_taken += 1
if rabbit == turtle:
return 'Loop found'
end-if
if steps_taken == step_limit:
steps_taken = 0
step_limit *= 2
// teleport the turtle
turtle = rabbit
end-if
end-forever
//Explanation: As we see that the turtle always sits at one position
// and rabbit moves to see if it meets the turtle. If it meets we
// have a cycle otherwise, let's just move the turtle directly to
// the position of rabbit instead of moving the turtle step by step
// as in Floyd's algorithm.
// We can see that such tele-porting of turtle would continue until the
// rabbit hits/enters the cycle. Once in side the circle it may happen
// that the rabbit still doesn't meet the turtle because the turtle is
// outside the loop (in fact haven't hit the loop yet). In such case
// turtle will be teleported again inside the loop skipping all nodes
// in between. Once both of them inside the loop, since turtle just
// sits there and rabbit makes moves, rabbit is bound to meet the turtle.
// If the step_limit is less than the loop size then even starting at inside
// the loop rabbit won't meet the turtle and the turtle will be teleported
// to a new location yet inside the loop. Since after each teleporting the
// step_limit increase (by two fold in this case), at some point of time,
// step_limit will be greater than loop length and then moving rabbit
// will move through the loop to meet the stationary turtle.
'shodnik' and 'Anonymous' have already provided solutions which I'm not fully convinced untill I receive some response against my asks to them.
In the mean time here is my solution in O(n) time and with fixed additional memory.
The only drawbacks of my algorithm is that it requires changing the structure of the list whereas both of the solutions from them does not. Note that the solution given by 'Anonymous' does a change of list structure but it can be avoided.
Anyway here is mine.
Use Robert W. Floyd's cycle detection algorithm with slight augmentation to determine if there exists any loop and if so then is there any self loop
If there is no loop
count length of the list
return length
else if there is any self loop
break the self loop by pointing to null
//i.e. a list head->A->B->B wud become head->A->B
count length of the list
return length
else
invoke countNode with head of the list
end-if
countNode(Node head)
if h==null or h->next null
return 0;
end-if
Node firstNode=null;
Node t=h->next;
while t!= null
Node t_dash=t;
t=t->next;
t_dash->next=null;
prepend(firstNode, t_dash);
end-while
return length(firstNode) -1 ;
end-function
prepend(Node firstNode, Node toAdd)
if firstNode==null
firstNode=toAdd;
return ;
end-if
Node temp=firstNode;
firstNode=toAdd;
firstNode->next=temp;
end-function
shodnik:
When I take a linked list head->A->B->C->D->C (i.e. D loops back to C) and try to apply your algorithm, I get stuck at line #4 of your algorithm.
If I set both pointers initially at head then by line#2 I see the pointers meet at node D.
Now I keep the hare pointer at D and reset the tortoise to head as mentioned in line#3. As you've mentioned I move tortoise pointer till I reach hare at node D. Anyway this is of no use since here is not pointing NULL.
So following line#4, we hit the 'else' part. The pointer tortoise is set to head again while here is still pointing to D.
Now moving both pointers takes me into an infinite loop.
Please help me understand what's wrong is happening here!!
'Anonymous' & 'Learner'
Can any one of you please elaborate this algorithm a bit more with below two cases!
Case 1) Head ->A->B->C->D->B i.e. D loops back to B
Case 2) Head ->A->B->C->D->C i.e. D loops back to C
For "case 1" when I applied your algorithm , I see both 'first' and 'second' pointers meet at C.
By splitting I get two list i.e breaking link C -> D, we get
Head->A->B->C
head2->D->B->C
Counting both lists yield, count1=3 and count2=3.
After this, I'm lost when you say "..Then start traversing two lists together till you reach at merging point. "
Can you explain what is the merging point in this case? Also didn't get what do you mean by "Then traverse the merged list." ! Which list is the merged list here?
drawbacks:
1) needs additional memory of complexity O(n).
2) finding address of a node might not be supported in some languages
In essence, not a very effective algorithm - one vote down.
While building min-heap what value you use - the value of the node or the occurrence of the node-vales? If you use former then you've a wrong answer and if you use occurrence then pls explain how do you get occurrence count for each node-value??
Sorry--making one vote down for missing this important info.
Anshul :
Can you pls. explain how a node's value has anything to do here!!
Yes 'maverick' you're right. This post essenially asking us to solve diameter
of a tree and I'm mistakenly solved it for longest path from root.
[Note: The diameter of a tree is the number of nodes on the longest path
between two leaves in the tree]
Anyway, here is a solution for finding leaves of a diameter - still with O(n)
complexity for both runtime and memory for a general tree (not necessarily a binary).
To explain the concept, let's take a binary tree (BT) first. For BT each node
can be assined a number which is sum of its left-height and right-hight. Thus
this number represents the longest path thru that node at which the sub-tree
is rooted.
Now if we identify a node from the original tree that has maximum value assigned
we can get the longest path in the orignal tree which is also the diamgeter of
the subtree rooted at this node. We can also get the two leafs - one from left-subtree
and one from right subtree of this node and it will give us the two leaves
with longest path.
If you've more than one nodes having max number assinged then all such node will
generate diameter of same lenth. Moreover for any node having max number assigned
may have more than one sets of diameter leaves since left subtree can have more
than one leaves at max-depth (min height) and likewise for the right subtree.
Now extending this concept to a generic tree, we can assume the number to assign
to a node is the sum of two maximum heights from all children's height. Rest of the
logic remains same.
Algorithm: [null check and edge condition checks are omitted for simplicity. A node is
assumed have a list of references to its children]
findADiameter(Node n)
// r will be node with max assigned value and
//c1 & c2 are children nodes having max heights.
Node r=null, c1=null, c2=null;
findMaxDepthAndUpdateResults(n, -1, r, c1, c2); //use pointer or so
//such that update of r, c1 and c2 by
//findMaxDepthAndUpdateResults gets reflected in parent.
Node leaf1=bfs(c1); //bfs returns one of the leaf max depth
//from sub-tree at c
Node leaf2=nfs(c2);
//leaf1 & leaf2 are the two leafs of a diameter of the original tree.
//There could exists other leafs having same diameter. With
//additional memory they can be captured as well.
end-function
int findMaxDepthAndUpdateResults(Node n, int dia, Node r, Node c1, Node c2){ //recursive function
int h1=-1; Node cc1=null;
int h2=-1; Node cc2=null;
//h1 & h2 will hold two max height of the all children's
// hight for parent node n
// h1 >=h2 will be maintained
if n->children == null
return 0;
end-if
for each child c in n->children
h=findMaxDepthAndUpdateResults(c, dia, r, c1, c2);
if(h >= h1 )
h2=h1 ; cc2=cc1;
h1=h; cc1=c;
else if (h >= h2 )
h2=h; cc2=c;
end-if
end-for
if ( number of children of n >= 2 )
if ( (h1+1 + h2+1) > dia )
dia=h1+h2+2;
c1=cc1; c2=cc2; r=n; //update the results
end-if
end-if
return max (h1, h2) + 1 ; //return height of the node n
end-function
Normally each node of a tree holds references either to its children or to it's parent. I'm wondering with any one of the structure of a node how you would perform two BFS's!!
If you assume each node knows it's children, then performing 1st BFS is easy and takes O(n) time where n=number of nodes. However once you get a leaf, how do you perform another BFS considering this leaf as root !!
Am I missing something!!
This post is in reference to my previous response above where I'm wondering why some links say that heapsort for linked list is nearly impossible.
Here I provide an algortihm that runs in O(nlogn) time. Most of the algortihm is taken from cormen's book except the method 'heapsort'
Pseudo algorithm and runtime calculation for heapsort (ascending order) for a linked list (with single forward pointer/ref)
-------------------------------------------------------------------------
heapsort(Node h) {//first time invoke this with head of the list
n=get_length_of_list(h); //runs in O(n)
build_max_heap(h); //runs in O(nlogn)
//handle max element of the entire list which would be the tail after sorting in ascending order
Node h_dash=h->next; //no additional node just a temporary variable thus fixed memory O(1)
h->next=h->next->next; //null check for h->next and returning is omitted for simplicity
h_dash->next=null; //ensure tail’s next field points to null
//now we keep on max_heapify the rest of the list and keep removing the max element from
// head of the given list and subsequently adding them to the head of the new list identified by
//h_dash
while h->next != null
max_heapfy(h); //runs in O(logn)
Node t=h_dash //another temporary variable ensuring O(1) memory
h_dash=h->next;
h->next=h->next->next; //null check not required since h->next is not null
h_dash=t;
end-while
//point the new list to the original head
h->next=h_dash;
----------------------------------
build_max_heap(Node h){ //runs in n times of runtime-of(max_heapfy) i.e. O(nlogn)
n=get_length_of_list(h); //this need not to be calculated again and can be passed as argument
for i from (n/2) downto 1 //indexing starts from 1 at head to n in the tail side.
max_heapify(h, i); //runs in O(logn) time
end-for
----------------------------------
max_heapify(Node h, int i, int n){ //see below
l=left_child_index(i) //runs in O(1)
r=right_child_index(i) //runs in O(1)
if l <= n and element_at(l) > element_at(i) //runs in O(n)
largest=l //we can also improve by storing the largest value in another variable, but omitted here
else
largest=i
end-if
if r <= n and element_at(r) > element_at(largest) //runs in O(n)
largest=r
end-if
if largest != i
swap element_at(i) with element_at(largest) //can be made O(1) we store relevant references during previous visits, but here it is O(n)
max_heapify(h, largest);
end-if
Run time of max heapify is:
T(n)= O(n) + O(n) + O(n) + T(2n/3) //with this algortihm
= O(n) + T(2n/3) //see cormen et. al. on why 2/3 of n
= O(nlogn)
Thus we see even for a linked list with forward pointer/ref we can have worst case heapsort time as O(nlogn) which is same as for an array.
The links geeksforgeeks.org/archives/7740 as well this one askville.amazon.com/scenarios-quicksort-faster-mergesort/AnswerViewer.do?requestId=1239017 state that quicksort performs poorly for linked list whereas heapsort is impossible for a linked list.
Like ‘Yateen’, am not yet fully convinced why quicksort works poorly. Conceptually I see quicksort for linked-list has avg. runtime of O(nlogn) just like for an array. As the later link hints that the nature of quick sort enforces a bi-directional traversing during portioning, it might cause cache misses for large sized linked list involving virtual memory (i.e. some data in secondary storage), I think it might be the reason but am not fully convinced yet. Any technical explanation on this or otherwise would be much appreciated!!
Moreover, I’ve no clue why the other sorting technique i.e. heapsort is impossible for a linked list. I can prove that a heapsort can be performed with O(nlogn) for a linked list just like for an array. To avoid cluttering I’m posting the pseudo algorithm and runtime calculation for heapsort for a linked list in a separate response at the bottom of this post (see below). Pls. enlighten me of any missing link causing the impossibility of heapsort in linked list!!
paulj91:
As far as favoring iterative solution to recursive solution is concerned I guess you are at one with me in your response.
However not sure what do you mean by ."..iterative counterpart due to its recursive nature." will NOT perform!! Would you please explain how the iterative solution by 'Anonymous' has recursive nature and why it won't perform for large data where recursive solution would fail with stack overflow!
wanted to share my thoughts... this solution is essentially a recursive version of 'Anonymous''s solution which is iterative in nature. It is so important to understand that recursive solutions are bound to fail with stack overflow when data size are huge. In essence always favor iterative solution to recursive one.
- buckCherry November 08, 2012@maveric:
Yes you're right, the given tree can be considered as a BST.
Note that wikipedia defines a BST only with no duplicate keys even though I don't agree with it. In fact all the authors including "Cormen et al" speak of BST in terms of the invariant I've mentioned.
Thus based on wiki this is not a BST, but based on my invariant and most of the authors this is a valid BST.
Thanks for sticking to your idea and pointing me to my earlier mistake.
@maveric:
Applying your idea the tree has root 3 which has another 3 as right child which in turn has 4 as right child. This 4 has another 3 as left child. To me this last 3 should not be the left child of 4 rather it should have been the parent of 4. Is there any explanation behind this!! I don't think I'm missing some specific order which might cause such form. Without any proper explanation this would still be a faulty BST.
@maverick:
Not sure what you intend to tell towards my post. Anyway let me first quote this excerpts from my post "..we expect a null value or something similar to be returned to indicate that the tree does not have any solution..".
So clearly null was just an option and I think you've missed out the "something similar" part of my post. Let me know if you still have any confusion!!
memo:
Your solution assumes that each node has a reference to its parent. What about the case where each node only knows its children!!
Whoever has voted this response down, I would appreciate a reasoning so that I can correct myself in future.
- buckCherry November 07, 2012Thanks CodeSpace for the response.
Unfortunately I've given a vote-down because the algorithm didn't consider a list of children (i.e. Node child = root.children; is incorrect as it should be something like List<Node> children=root.children)
AK:
Building a BST by adding 13, followed by 6, followed by 9,..finally by adding 11, we'll have a tree whose root =13. Root=13 will have only left child=6. 6 will have 9 as right child, 9 in turn will have 10 as right child and finally 10 will have 11 as right child.
With this BST, if you apply 'Duke87''s algorithm, then the value of nextBig
after 1st iteration is : 13 (since 13 > 9 )
after 2nd iteration is : 13 (i.e. unchanged since 6 < 9 )
after 3rd iteration is : 13 (i.e. unchanged since 9 > 9 is false)
after 4th iteration is : 10 (since 10 > 9 )
Thus final answer is 10 (not 11).
Let us know how did you get 11.
AK:
Unless you write a pseudo code, it's very difficult to evaluate the correctness of your solution. In addition, see my response above, where I think you've mistaken got wrong answer for a tree with 13 6 9 10 11.
Not sure why you're using data as input param and checking if a node's value is same as data.
- buckCherry November 07, 2012Even though recursive solution should be avoided as much as possible since for large tree they are bound fail with stack overflow, here is the pseudo code for recursive solutions:
dfs_recursive (Node n){
if n==null
return;
end-if
if n has children
for each entry c in n->children
dfs_recursive(c);
end-for
end-if
print n; //post order DFS
}
bfs_pre_recursive {
Q <-- initialize a queue
Node marker <-- initialize a node
Q.enqueue(root);
Q.emqueue(marker);
bfs_recursive(Q, marker);
}
bfs_recursive (Queue Q, Node MARKER) {
while true
Node n=Q.dequeue();
If n is MARKER
break;
end-if
print n
if n has children
for each entry c in n->children
Q.enqueue(c);
end-for
end-if
end-while
if Q is not empty
Q.enque(MARKER);
bfs_recursive(Q, MARKER);
end-if
}
@ kaush:
I fully agree with Godel - pls be rigorous about your post.
Additionally, you've mentioned about moving left to right in a tree and this to me is a horizontal movement rather than a verticat one.
Here is a pseudo code that runs with O(n) memory and O(n) time complexity. Conceptually it’s a breadth-first-traversal with queue.
I’ve used an additional queue to hold the leafs for final answer.
Algorithm -Starts
Node marker <-- create a node object // this acts as delimiter of each levels nodes
Q1 <- initialize an empty queue
Q2 <- initialize an empty queue
//For each node removed from Q1 its children are stored again in Q1. If the removed
//node doesn’t have any children then only it will be queued to Q2.
//The loop exits when Q1 is empty and at that time all nodes in Q2 are the leafs of all longest paths from root.
Q1.enqueue(root);
Q1.enqueue(marker);
While true
Node n=Q1.dequeue();
If n is marker
If Q1 is empty
Break;
Else
Q1.enqueue(n);
Q2.removeAll();
continue
End-if
End-if
boolean hasChildren=false;
if n has left child
Q1.enqueue(n->leftChild);
hasChildren=true;
end-if
if n has right child
Q1.enqueue(n->rightChild);
hasChildren=true;
end-if
if hasChildren == false
Q2.enqueue (n);
End-if
End-while
//all nodes in Q2 are the answer
Algorithm –Ends
The given tree in input 2 is NOT a BST. A BST must maintain an invariant that given any node, all nodes in the sub-tree rooted at the given node must follow some kind of order, say all nodes in the left side of the root of the sub-tree must be less than the root (given node) and similarly all nodes from right side of the sub-tree must be greater than the root (given node). For a BT to become a BST this invariant must be true for all sub-trees rooted at all of its nodes. The tree in example 2 doesn’t follow this invariant as it has root 3 which has node 5 on its left. I think ‘pradegup’ has already noticed this anomaly – kudos to him.
However the question can still be valid for either a BT or a BST. In both cases a traversal of tree along with comparing duplicate check and maintaining their count can be done in theta(n) time. In case of BT I think additional memory in the form of hash-table like data structure would be required in maintaining the duplicate key’s count. However for BST we don’t need any additional memory if we maintain a collection of values for duplicate keys ensuring even a duplicate key occurs only once in the tree (but they may have more than one value per duplicate key). Anyway the idea is that with actual implementation of a BST with duplicates the need for additional memory (Hash-table) may go away whereas for BT additional memory is essential.
Extending the response from ‘axecapone’, I think too that binary tree is just a representation of parent child relationship and thus duplicate key is most likely unnecessary. However if a duplicate key in a particular case tends to break the invariant of parent child relation in that case each node should maintain collection of values corresponding to colliding keys (keys with same value). If for a non-duplicate binary tree, a node is represented by three parameters – leftChild, rightChild and value then with duplicate keys a node should be modified to hold a collection of values. In addition appropriate data structure such as linked list or set or the likes should be used for holding collection of values corresponding to duplicate keys.
- buckCherry November 07, 2012Duke87,
Your algorithm is conceptually correct, but for the sake of completeness you might like to consider addressing the below case which currently will return wrong answer.
Consider a tree with single node whose value is INT_MIN. In this case we expect a null value or something similar to be returned to indicate that the tree does not have any solution but your solution will return INT_MIN which is the value of the root node and is incorrect answer.
In your algorithm when you find xyz from the merge-sorted combined list, how do you find closest xyz so that each number belongs to each original list! In fact that's the catch of this question!!
- buckCherry October 20, 2012I think the algorithm works and we don't need additional memory to store all the tuples of closest numbers for each elements of the list with smallest size. However this method is so brute force and it benefits only when the size of list with smallest size is relatively very less than sizes of rest two lists. Let's get a bit deeper into the run time calculation to understand this.
If we assume the lists are of sizes k, m, n and k is min of the three lists, then the run time is k(logm+logn). For each element from a list, searching closest elements from other lists takes (logm+logn) and we repeat this for k times. Now we can see that this is better than k+m+n only when k <<< m and k <<< n [ <<< means very less].
Even though the concept mentioned by you is correct (in fact same as previous Anonymous comment) I think the ordering of algorithm is incorrect.
The line "find which list[index] is minimum among i, j, k then increase that index by 1" should have been after minVal check & update, otherwise it gives a wrong idea that at each step we first find out the index with min value and increment that index after which we do a minVal > (max (..) - min (..)) check with elements at updated index.
This is a non-recursive code.
- buckCherry January 31, 2013