I haven’t learned how to compute these values in class, and want to try my hand at them before looking up solutions. My reasoning for finding the minimum depth is as follows (Assume we have a class BST, where an instance of this class has fields root, left, right, where left and right are instances of BST and root is an instance of a node class, which has an integer data field).
- Check if the root is null. If so, return 0.
- Get the minimum depth of the left subtree and right subtree.
- Find the minimum of the two
- The minimum depth would be 1 + this minimum, since we need to account for the root.
In code, this would be:
public int minDepth(BST tree){ if (tree.root == null) return 0; int leftDepth = minDepth(tree.left); int rightDepth = minDepth(tree.right); return 1 + min(leftDepth, rightDepth); }
My reasoning for maxDepth is very similar; we can literally just replace all occurences of min in the above code with max (i.e. minDepth becomes maxDepth, min(leftDepth, rightDepth) becomes max(…) ) and the reasoning should still hold. Is this a correct way to go about the code? Is there a cleaner/faster way to do the computations if so?