How Deep Does It Go? Maximum Depth of Binary tree

Write a method to determine how deep a binary tree goes. The tree's depth can be described as the number of nodes you encounter as you traverse from the root node to a leaf.

The root node is the topmost node, and a leaf is a node with no children.

For example, you're given the following binary tree:

    6
   / \
  2  14
    /  \
   13   19

The longest distance is from 6 to 19, and we return 3 because it covers 3 nodes.

The method will be invoked like the following:

const root = new Node(6);

function howDeep(root) {
    return;
};

howDeep(root);

Constraints

• Number of nodes in the tree <= 100000
• The nodes will always contain integer values between -1000000000 and 1000000000
• Expected time complexity : O(logn)
• Expected space complexity : O(n) considering the call stack

```js
function howDeep(root) {
  // Fill in this method
  return root;
}
```

This seems like a pretty straightforward problem: we essentially want to just count the maximum number of levels that the tree has. There's several ways to do this, but we'll need to traverse the tree.

Given that it's a binary tree, this means that there's up to two paths to move -- left and right. This fact simplifies things a bit, as traversal just requires navigating two children at each node.

During traversal, we can detect a leaf either when there is no left or right:

```js
if (!node.left && !node.right) {
  return;
}
```

Or we could simply return when there is no node at all.

```js
if (!node) {
  // if parent returned twice here (left/right), it was a leaf
  return;
}
```

At every node, we can recursively traverse down the left and right children if they exist, until we reach a leaf.

The difficult part is keeping track of the number of levels.

To do that, we can make the return statement the number of levels thus far, and increment it by 1 at every step.

This solution has a time complexity O(log n).

One Pager Cheat Sheet

• Write a method to calculate the depth of a binary tree using O(logn) time complexity and O(n) space complexity.
• We can traverse the binary tree to count its maximum levels by navigating two children at each node and detecting a leaf when a left or right does not exist.
• We can return when there is no node present.
• We can recursively traverse down the left and right children of each node until we reach a leaf, returning the number of levels traversed and with a time complexity of O(log n).