Understanding this code of Binary Search Tree Implementation through Array

Oct 19, 2019 at 5:26pm
Oh My, sorry... Got it wrong totally.. Please delete this
Last edited on Oct 19, 2019 at 5:43pm
Oct 19, 2019 at 5:42pm
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.
Last edited on Oct 19, 2019 at 5:49pm
Oct 19, 2019 at 5:44pm
Oh, yes, you pointed it out too... Yes, thank you... I was thinking it wrong
Oct 21, 2019 at 3:44pm
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.