A binary tree node has a value and up to two children. Most tree problems have the same shape: answer the question for the left subtree, answer it for the right subtree, and combine the two at the node. The empty tree is the base case.
Some questions are about levels instead. Breadth-first traversal handles them: keep the nodes of one level, process them all, and collect their children as the next level.
A binary search tree adds a rule: everything left of a node is smaller, everything right is larger. Checking it needs more than a node and its children, so pass the allowed range down as you go.
Recursion costs O(h) stack space, where h is the height. Test an empty tree, one node, a tree leaning to one side, negative values and, in Java, sums or bounds that pass the int range. In the tests, trees are written level by level with null for a missing child.
root = [10, 4, 12, null, 6, null, null, 5]
10
/ \
4 12
\
6
/
5
depth(5) = 1, depth(6) = 2, depth(4) = 3, depth(12) = 1
depth(10) = 1 + max(3, 1) = 4
Each node adds one level to the deeper of its two subtrees.