Understanding this code of Binary Search Tree Implementation through Array

Oh My, sorry... Got it wrong totally.. Please delete this
Last edited on
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
Oh, yes, you pointed it out too... Yes, thank you... I was thinking it wrong
Please don't go deleting your question after you've received an answer. It makes the thread incomprehensible to anywone else who reads it.
Registered users can post here. Sign in or register to post.