What would the time complexity of this algorithm be?

1. Finding tree height is O(n).

If getHeight is more or less the following, it will be O(n), where n is the number of nodes in the tree:

static int getHeight(Tree tree) { if (tree == null) { return 0; } return 1 + max(getHeight(tree.left, tree.right)); } 

2. Storing the coordinates for all elements in the hash map O(getTreeCoordinates) = O(height * n) right now, but can be improved to O(n).

O(HashMap.putAll) technically depends on implementation, but is almost certainly linear in the number of elements! Instead of using HashMap.putAll, you can pass the HashMap down to the recursive calls, e.g.:

static HashMap<Coordinate, Integer> getTreeCoordinates(Tree tree, int x, int y, int maxWidth){ HashMap<Coordinate, Integer> result = new HashMap<>(); return getTreeCoordinatesImpl(tree, x, y, maxWidth, result); } static void getTreeCoordinatesImpl(Tree tree, int x, int y, int maxWidth, HashMap<Coordinate, Integer> result){ result.put(new Coordinate(x, y), tree.data); if (tree.right != null){ getTreeCoordinatesImpl(tree.right, x+maxWidth/(int)Math.pow(2, y+1) + 1, y+1, maxWidth, result); } if (tree.left != null){ getTreeCoordinatesImpl(tree.left, x-maxWidth/(int)Math.pow(2, y+1) - 1, y+1, maxWidth, result); } } 

3. Printing the coordinates to the screen is O(height * width). It will be O(n), where n is the number of nodes is the tree, if you iterate over the HashMap instead of over all (x, y) coordinates.

Both O(HashMap.containsKey) and O(HashMap.get) are 1 (constant time). To be precise, they're amortized constant in time - on average, they take a constant time, but a single run can be linear in the number of elements of the hash map in the rare worst case.

In big O notation all constants are equivalent (O(1) is equivalent to O(2)). So:

O(printCoordinatesToConsole) =

O(height) * O(width) * (O(HashMap.containsKey) + O(HashMap.get)) =

O(height) * O(width) * O(1) =

O(height * width)

Now, since width is 2^height, which in the worst case would be n, does this mean the time complexity is O(n*2^n)?

Let's do the math (n is the number of nodes in the tree, I assume getTreeCoordinates is edited as described above):

O(printTree) =

O(getHeight) + O(getTreeCoordinates) + O(printCoordinatesToConsole) =

O(n) + O(n) + O(height * width)

Since height * width >= n:

O(printTree) = O(height * width)

Also, if I were to ignore the printing (or if I were to print directly to the coordinates on the console rather than iterating through all of the width/height), would the complexity then be O(n)

Yes, then the above equation becomes either (no printing):

O(printTree) = O(getHeight) + O(getTreeCoordinates) = O(n) + O(n) = O(n)

or (printing with iteration over the hash map of nodes):

O(printTree) = O(getHeight) + O(getTreeCoordinates) + O(n) = O(n)

It will be helpful if you include the definitions of Tree, Coordinate and getHeight, and if applicable, the contents of tree. You can also use an online playground like ideone.com to provide a runnable example.