1

I have a vector of parent pointers [ 0 1 1 2 2 3 3 5 5 ....] which is basically a binary tree. The index is the child and the corresponding value represents the index of its parent in the same vector.

e.g: in the above vector, if you count to index 5, the element is 2, which means that its parent lies at index 2. Again at index 2, the element is 1 which means the parent lies at index 1. At index 1 is the element is 0 which is the root node.

How can I create a binary search tree from this?

OR,

I am generating data in binary tree format in which I know the parent and corresponding children, how can I store them in a binary search tree?

Index for children will always be greater than the parent, as shown in the vector above. An example is: I take node 1, divide it into two nodes, 2 and 3. Then take node 2 and divide it into 4 and 5. Then I take node 4 and divide it into 6 and 7 and so on. I want to keep the parent child relationship in the binary search tree.

Best Regards

Wajahat

3
  • 1
    What is the question? I don't see a question mark in the post...
    – iwein
    Oct 21, 2012 at 20:01
  • Sorry, now you can identify question easily.
    – Wajahat
    Oct 22, 2012 at 20:39
  • thanks, much clearer now
    – iwein
    Oct 23, 2012 at 5:55

1 Answer 1

0

Generate a binary tree with empty elements according to you specification in the vector. Upon new element arrival, find a place to put it: traverse the tree according to binary search tree rules - all the children in the left subtree are smaller than an element and all the children in the right subtree are larger. Fill the node corresponding to the element in the binary tree. E.g., if you have this tree at some point of time:

and new value 3 arrives, it will fill the right child of node with value 2. However, if 5 arrives, there is no place to put it in the predefined tree structure.

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.