kd-tree stores points in inner nodes? If yes, how to search for NN?
Without storing points in the inner nodes, but the cut value and cut coordinate, one can use this algorithm to perform NN search:

Procedure NN(node), given query q
  if(node is leaf)
    Search all points, in node, update current best
  else {internal node}
    if( cut_coord(q) &lt;= node's cut-value )
        NN(left-child)
        if( cut-coor(q) + current best distance &gt; node's cut-value )
            NN(right-child)
        end if
    else {cut-coor(q) &gt; node's cut value}
        NN(right-child)
        if(cut-coor(q) - current best distance &lt;= node's cut-value)
            NN(left-child)
        end if
    end if(left/right)
  end if(node)


In order to perform ANN search, see the answer here.