Balanced Binary Tree

Balanced Binary Tree - LeetCodeLeetCode

Problem

Given a binary tree, determine if it is height-balanced.

Example 1:

Input: root = [3,9,20,null,null,15,7]
Output: true

Example 2:

Input: root = [1,2,2,3,3,null,null,4,4]
Output: false

Example 3:

Input: root = []
Output: true

Pseudocode

recurse over left and right node
 - return 0 when recursion reaches the end of tree
 - return the max height of left and right sub-tree + 1
  - if difference is more than 1, return false

bfs approach is also possible, but dfs is more suited as it finds DEPTH FIRST SEARCH.

Solution

var isBalanced = function (root) {
  let result = true;

  if (!root) {
    return true;
  }

  function walkMetrics(node) {
    // base condition
    if (!node) {
      return 0;
    }

    // pre
    // recurse
    let walkLeft = walkMetrics(node.left);
    let walkRight = walkMetrics(node.right);

    // post
    if (Math.abs(walkLeft - walkRight) > 1) {
      result = false;
    }

    return 1 + Math.max(walkLeft, walkRight);
  }

  walkMetrics(root);

  return result;
};

Time and Space Complexity

Time

• Recurse to find the max depth and compare the max height of left and right subtrees. Scales linearly with input size all nodes are visited. O(N)

• Total - O(N)

Space

• Memory requirements of recursive stack also scales linearly to input. O(N)

• Total - O(N)