Do level order traversal until we find an empty place .
while ( q . Count != 0 ) { temp = q . Peek ( ) ; q . Dequeue ( ) ; if ( temp . left == null ) { temp . left = new Node ( key ) ; break ; } else q . Enqueue ( temp . left ) ; if ( temp . right == null ) { temp . right = new Node ( key ) ; break ; } else q . Enqueue ( temp . right ) ; } }