Interview Question: Random Binary Tree

In this video, I show how to implement a method that returns a random node in a binary tree

Do you have a big interview coming up with Google or Facebook? Do you want to ace your coding interviews once and for all? If so, Byte by Byte has everything that you need to go to get your dream job. We've helped thousands of students improve their interviewing and we can help you too.

You can also find me on

[anuragdani]

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.!

[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.

[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.

[berylbose]

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?

[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?

[chiamarc]

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.

[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

[RaymondLo]

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

[HimanshuSharma-tmms]

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:)

[piyush]

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

[ivanpetrov]

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

[sanjutoyou]

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

[snoopyjc]

Nice but... There is no randomNode function!