CODEWITHSUNDEEP
javaalgorithmrandomdata-structuresbinary-tree
topsyl
topsyl

Reputation: 53

Binary Tree - Random Generator

Suppose I have a Binary tree like this -

       5               
      / \       
     /   \      
    /     \     
   /       \    
   2       8       
  / \     / \   
 /   \   /   \  
 1   3   6   9   
      \   \   \ 
      4   11   10

Now I have a random generator which will generate a number between 1 to size of tree (10 in this case). Based on the random value generated by the random generator I have to return the node from the tree(Suppose, generator given 7, so I return the 7th node(value 11), doing inorder traversal). Tomorrow I add 4 more nodes to the tree. How do I maintain the consistency? As in, the same node from the tree is returned for the random value. The inorder traversal will create a different array and the value of the index will change.

Upvotes: 0

Views: 1388

Answers (2)

Erik P.
Erik P.

Reputation: 1627

One option would be to just add any new nodes as right children of the last node in the in-order traversal. This will lead to a very deep and unbalanced tree; you didn't ask for a balanced tree, so it's possible that that's OK.

Upvotes: 1

ajb
ajb

Reputation: 31699

Your question doesn't really make sense unless your goal is to construct a binary tree by adding nodes to it, and freezing the mapping between indexes and nodes at a certain point, so that future additions to the tree (after the freezing point) don't change that mapping.

It still isn't clear what you are trying to accomplish, but I can see a couple possibilities. If your intent is that new nodes can be added anywhere in the tree, then they really can't have any indexes that map to them sensibly. In that case, I would just create a map (e.g. a HashMap) at the freezing point, to map the indexes to the nodes. Traverse the tree with an in-order traversal, build the map, and save it together with the tree structure. Use the map to determine the node for an index, rather than traversing the tree.

If, instead of adding nodes anywhere in the tree, you want to add nodes in a place so that the original nodes will still have the same index, then all you need to do is go down the tree's right children until you hit a node with no right child. In your posted example, that would be the node 10:

       5               
      / \       
     /   \      
    /     \     
   /       \    
   2       8       
  / \     / \   
 /   \   /   \  
 1   3   6   9   
      \   \   \ 
      4   11   10**

Mark that node at the point where you want to freeze. Then, when you add a new node, the new node must be added as either the right child of the marked node--or if the marked node has a right child R (since you've already added one after freezing), anywhere where it will be a descendant of R. New nodes added in this way will always succeed, in an in-order traversal, the nodes that were present at the freezing point. Thus the indexes of the previously added nodes won't be affected.

If neither of these is what you want, you will need to provide more clarification about what you need.

Upvotes: 5

Related Questions