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).

This is our final solution.

To visualize the solution and step through the below code, click Visualize the Solution on the right-side menu or the VISUALIZE button in Interactive Mode.

xxxxxxxxxx

}

var assert = require('assert');

​

function howDeep(root) {

  if (root === null) {

    return 0;

  }

​

  return Math.max(howDeep(root.left), howDeep(root.right)) + 1;

}

​

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);

​

var tree4 = new Node(5);

Great job getting through this. Let's move on.

If you had any problems with this tutorial, check out the main forum thread here.