Interview Question: Random Binary Tree

[@anuragdani9739]

The main difference that I found in your videos and other is that you do explain the thought process and approach to solve the problem and explain why they might not be the optimum solution for the problem that you are trying to solve. It would seem like a very trivial point, but this does give a direction for thinking in general problem and this is what separates from you other similar videos online. Keep this up, and I am very sure you will be highly successful in your current venture.!

[@ByteByByte]

anurag dani thanks! That's exactly what I'm going for so I'm glad it's coming across and that you are finding it helpfil

[@sharjeeltahir5583]

There are other people who do the same

[@sammyiboi]

Hi Sam! Before you went into your explanation, I was trying to brainstorm a solution. And, I came up with "somehow" giving each node a certain weight value. For example, the root of the tree would get a low weight value so more than likely, a randomly generated value would not match it. And then it would traverse down to one of its children. And.. ahh, even trying to type this quasi-solution is giving me a headache! I think the trickiest part is remembering that we can "take control" of our data structure (e.g. "Can I assume that the Node class has a 'children' field?") It's a great thinking-outside-the-box approach that not only makes the solution more elegant but also shows the interviewer that you think critically about the assumptions of a question. Anyway, thanks for the vid! Hoping to watch 1 or 2 everyday as interview prep.

[@ByteByByte]

You're welcome! That's awesome to hear that you got some valuable insight from the video :)

[@PabitraPadhy]

@bytebybyte : Assume, I'm not modifying the tree structure, and calculates the GetChildCount() during runtime. So, for a dense tree, it would result me : { O(h) + O(h/2) + O(h/4) + ....} = O(h logh) and for a skew tree, it would result me : O(h^2) If I use this algo (with dynamic child count) Now, let's assume, your tree is going to add/delete nodes frequently, so we have to recalculate the child count, say worst case O(n). So, I believe, you're taking tree to have correct child node, when you're running the GetRandomNode() algo, that would make it O(h) Correct me, if I'm wrong.

[@MegaModelina]

Thanks Sam! Altho lengthier, would it also work to have a separate rightChildren() that also adds the length of left subtree + parent node, in order to keep the indexing the same throughout? Could then pass which fxn to use as parameter. Please lmk

[@berylbose7006]

Can we give an index to each of the nodes, in IN-ORDER fashion, like a bst. and when we traverse, we will be doing a bin search to get the node with the index we are looking for. If this a valid approach?? Does my approach have the same time complexity as yours?

[@Famctabe]

Hi Sam, if you were given a perfect binary tree could you eliminate the extra storage for the children count? As long as you know the size (or height), you'd know where the random index lies because it's symmetrical.

[@ByteByByte]

that's a good question. you would at the very least need to know the total number of nodes in the tree (although you could track that as a single int). I think it would work if you knew that you had a perfectly balanced tree, but as soon as you add or remove any nodes, then your tree is no longer perfectly balanced so it's a somewhat narrow usecase

[@gentleflameoflove]

This video is more to do with random selection from a binary tree, doesn't it Sam? Does it discuss the 'random binary tree' data structure as such?

[@ByteByByte]

What do you mean by 'random binary tree datastructure'?

[@HimanshuSharma-tm2ms]

You are still using O(n) in the best solution cause you are storing no of children in each node.. but than logn trick was good:)

[@piyush12121]

Hey, Awesome video. Can I say that you're basically doing an Inorder traversal of the tree to find the random value ?

[@ByteByByte]

Thanks! I gotta disagree. Really the whole idea is not to do the full inorder traversal. Rather we're treating the tree as ordered and doing a binary search for the index. Inorder traversal would mean traversing all the nodes until we get to an index, which we are explicitly trying not to do

[@piyush12121]

Cool !

[@RaymondLo84]

Is that a typo? randomNode is never defined? You may getRandomNode?

[@sanjutoyou]

Hey what is the case when this tree will return root node i.e. 4

[@ByteByByte]

if the number generated was 3, then you would find that the root had 3 children on the left and so you would return immediately

[@ivanpetrov3200]

Why don't you just at each step choose randomly left or right?

[@kevinjad4506]

Hey, Ivan. We would be calling the random number between flag_right and flag_left more than one time which is costly.

[@sivaprakashnithyanandam1473]

Very lengthier............

[@snoopyjc]

Nice but... There is no randomNode function!

[@RaymondLo84]

it should be getRandomNode