- Forum
- General C++ Programming
- Binary Search Tree
Binary Search Tree
Any suggestion for
How do you put a Binary Search Tree in an array in an efficient manner.
Hint :: If the node is stored at the ith position and its children are at 2i and 2i+1(I mean level order wise).It's not the most efficient way.
How do you put a Binary Search Tree in an array in an efficient manner.
Hint :: If the node is stored at the ith position and its children are at 2i and 2i+1(I mean level order wise).It's not the most efficient way.
Do you know what a binary tree is? If you don't you need to find out.
If you do, you'll know that it's a tree with at most two nodes. So the maximum number of nodes you can have at each level is 1, 2, 4, 8, ... you sum the series to get the total size.
Instead of allocating each node, the whole thing can be stored in an array. Got it?
If you do, you'll know that it's a tree with at most two nodes. So the maximum number of nodes you can have at each level is 1, 2, 4, 8, ... you sum the series to get the total size.
Instead of allocating each node, the whole thing can be stored in an array. Got it?
Last edited on
I know about binary tree very well. But my question is different my friend..
and i also know and implemented Binary Search Tree with logic If the node is stored at the ith position and its children are at 2i and 2i+1(I mean level order wise). But now they are saying that is not efficient way i am wondering about efficient way.
and i also know and implemented Binary Search Tree with logic If the node is stored at the ith position and its children are at 2i and 2i+1(I mean level order wise). But now they are saying that is not efficient way i am wondering about efficient way.
You can have an array of pairs! the first element would contain the indexes of the 2 children of the root, and at those indexes you have more pairs etc. And the values would be in a seperate array, so the children and the value are at the same indexes. Or, you can have the array be a pair of an int and a pair, so the first element would be the value, and the second would be a pair of the children's indexes.
| But now they are saying that is not efficient way |
Topic archived. No new replies allowed.