- Forum
- General C++ Programming
- Understanding this code of Binary Search
Understanding this code of Binary Search Tree Implementation through Array
it appears to use -1 as 'null' 'pointer' (sentinel for the index).
that is your terminal condition, its right there in the prints... ?
if (arr[n] != -1)
the class constructor loads the whole array with -1s so anything not used (by insert) is still -1. The tree can't store a -1 as a value, though, this usual issue with sentinels.
I prefer to have left/right be array indices as 'pointers' and set THOSE to -1 (while you can have negative array index when doing pointer magic, its not valid so its safe) and use a traditional 'pointer' design instead. This 'tree' solves the problem of printing your data in the 3 orders but the avoidance of a pointer chain like concept makes it not a great design or example of the idea. It would be weird to code a binary search tree from this class.
that is your terminal condition, its right there in the prints... ?
if (arr[n] != -1)
the class constructor loads the whole array with -1s so anything not used (by insert) is still -1. The tree can't store a -1 as a value, though, this usual issue with sentinels.
I prefer to have left/right be array indices as 'pointers' and set THOSE to -1 (while you can have negative array index when doing pointer magic, its not valid so its safe) and use a traditional 'pointer' design instead. This 'tree' solves the problem of printing your data in the 3 orders but the avoidance of a pointer chain like concept makes it not a great design or example of the idea. It would be weird to code a binary search tree from this class.
Last edited on
Please don't go deleting your question after you've received an answer. It makes the thread incomprehensible to anywone else who reads it.
Topic archived. No new replies allowed.