algorithm - Sentinel node in Binary Search Trees -

i wondering if in way avoid having deal root special case in binary search tree use sort of sentinel root node?

public void insert(int value) {     if (root == null) {         root = new node(value);         ++size;     } else {         node node = root;         while (true) {             if (value < node.value) {                 if (node.left == null) {                     node.left = new node(value);                     ++size;                     return;                 } else {                     node = node.left;                 }             } else if (value > node.value) {                 if (node.right == null) {                     node.right = new node(value);                     ++size;                     return;                 } else {                     node = node.right;                 }             } else return;         }     } } 

for instance, in insert() operation have treat root node in special way. in delete() operation same happen, in fact, way worse.

i've thought bit regarding issue couldn't come solution. because not possible or missing something?

the null node sentinel, instead of using null, can use instance of node special flag (or special subclass), null node. nil node makes sense, valid tree: empty!

and using recursion can rid of checks , new node littered on (which presume bothering you).

something this:

class node {   private value v;   private boolean is_nil;   private node left;   private node right;    public void insert(value v) {     if (this.is_nil) {       this.left = new node(); // nil node       this.right = new node(); // nil node       this.v = v;       this.is_nil = false;       return;     }     if (v > this.v) {       this.right.insert(v);     } else {       this.left.insert(v);     }   } }  class tree {   private node root;   public tree() {     root = new node(); // nil node.   }   public void insert(value v) {     root.insert(v);   } } 

if don't want use recursion, while(true) kind of code smell.

say keep null, can perhaps refactor as.

public void insert(value v) {   prev = null;   current = this.root;   boolean left_child = false;   while (current != null) {     prev = current;     if (v > current.v) {       current = current.right;       left_child = false;     } else {       current = current.left;       left_child = true;     }   }   current = new node(v);   if (prev == null) {     this.root = current;     return;   }   if (left_child) {     prev.left = current;   } else {     prev.right = current;   } }