AlgoDaily - How Deep Does It Go? Maximum Depth of Binary tree

How Deep Does It Go? Maximum Depth of Binary tree (Medium)

Good morning! Here's our prompt for today.

You may see this problem at Google, Flipkart, Lyft, Ebay, Workday, Reddit, Tesla, Citadel, Coinbase, Sap, Bosch Global, Zoho, and Electronic Arts.

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:

JAVASCRIPT

1    6
2   / \
3  2  14
4    /  \
5   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:

JAVASCRIPT

1const root = new Node(6);
2
3function howDeep(root) {
4    return;
5};
6
7howDeep(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

xxxxxxxxxx
​
 
var assert = require('assert');
​
function howDeep(root) {
  // Fill in this method
  return root;
}
​
function Node(val) {
  this.val = val;
  this.left = null;
  this.right = null;
}
​
// Regular binary trees
var tree1 = new Node(4);
tree1.left = new Node(1);
tree1.right = new Node(3);
​
var tree2 = new Node(5);
tree2.left = new Node(10);
tree2.left.left = new Node(17);
tree2.left.right = new Node(3);
tree2.right = new Node(8);
​
// Binary search trees
var tree3 = new Node(6);
tree3.left = new Node(3);

OUTPUT

Results will appear here.