• what is a node?
• the root is the topmost node
• tree with a property that each node in the tree can have AT MOST 2 children
• nodes have either 0,1,2 children
• we call one of the children the left child and the other the right child. if there is no child, you just set the particular child to null!

if anyone is having confusion between depth and height, think of the analogy that we measure the 'depth' of sea from it's surface and the 'height' of a person from toe to head.

PS: This was taken from a stackoverflow thread.

In this case, we should have each method call represent one instance of the definition of our binary tree. That is, it should either deal with the case where we are at the empty tree, or it should deal with the case where we are at a node with potentially left and right subtrees.

In order to do this, we need some way to keep track of where we currently are in the tree at the time the recursive method is called. Since we have no way of doing this with just the public method, we introduce a private helper method that takes in an IntTreeNode parameter that represents the current node we are at (this is exactly like what we did in the print method in class).

Remember, recursive methods have two parts, a base case and a recursive case. We can use the recursive definition of a binary tree to help us spot what our base case should be and what our recursive case should be. Let’s start with the base case.

Remember, we want the base case to be the simplest, most basic version of the problem at hand that we can solve almost immediately. What’s a simple tree for which we can immediately tell if it contains our value? The empty tree is simple since we know that the empty tree can’t contain our value. How do we know if a tree is empty? If it is null then we know there are no nodes in our tree, and thus it is empty. We can then signify that it doesn’t contain our value by returning false. The following is a good base case

How should we link the two recursive calls on the subtrees together? Sometimes it can help to describe what we want to return in order to figure out how to link the recursive calls together. If the current node does not contain the value (this means we are in the else branch), then we want to return true if the left subtree or the right subtree contains the value. Thus we can use the logical operator || to complete our private helper method: