Methods and apparatus are disclosed for enhancing a binary weight neural network using a dependency tree. A method of enhancing a convolutional neural network (CNN) having binary weights includes constructing a tree for obtained binary tensors, the tree having a plurality of nodes beginning with a root node in each layer of the CNN. A convolution is calculated of an input feature map with an input binary tensor at the root node of the tree. A next node is searched from the root node of the tree and a convolution is calculated at the next node using a previous convolution result calculated at the root node of the tree. The searching of a next node from root node is repeated for all nodes from the root node of the tree, and a convolution is calculated at each next node using a previous convolution result.