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