Find the max depth of a binary tree

graph-theory-max-depth-binary-tree.md

Graph Theory

Get the Height of a Binary Tree

Also described as ...

1. Find the Maximum Depth of a Binary Tree

2. Find the sum of all nodes of a Binary Tree

---

Concept

Obtain the height of the tree without iterating over each node.

Time Complexity: o(n)

---

Approach

Using a recursive method. Find the maximum depth for the node, starting with root.

PSUEDO-CODE

START_FUNCTION TreeOfNodes getHeight(Node activeNode):

  // Default Height to Zero Depth
  HEIGHT = 0;

  IF (activeNode does not exist) THEN
    // (of zero)
    RETURN HEIGHT;
  END IF

  START SUB-ROUTINE: GET_HEIGHT_OF_CURRENT_NODE
    // using Math.max(), RETURN THE GREATER
    // OF THE TWO VALUES, (INT A, INT B)
    HEIGHT = MATH.MAX(
                // INT A
                getHeight(Node activeNode.left),
                // INT B
                getHeight(Node activeNode.right)
            )
  END SUB-ROUTINE

  // ADD a value of 1,
  // account for the currently Active Node
  RETURN 1 + HEIGHT;

END_FUNCTION

Using the maximum depths of the left and right tree nodes, find the maximum of the left and the maximum of the right, and add that to 1 (for the root node), as a way to find the maximum height of a tree.

(() => {

  class Bst {
    treeHeight(root) {
      if (root == null) return 0;
      return (
          (left, right) =>
            Math.max(this.treeHeight(left), this.treeHeight(right))
          )(
            root.left, root.right
          )
        + 1;
    }
  }

  class BstNode {
    constructor(data = null) {
      this.data   = data;
      this.right  = null;
      this.left   = null;
    }
  }

  // builder - main function
  (function main(bst, bstNode){
    let expected = 5;
    let root                    = new bstNode(5);
    root.left                   = new bstNode(10);
    root.left.right             = new bstNode(25);
    root.left.right.right       = new bstNode(35);
    root.left.right.left        = new bstNode(30);
    root.left.right.left.left   = new bstNode(20);
    root.right                  = new bstNode(15);

    let tree = (new bst().treeHeight(root));

    console.log(`Binary Tree has a height of: ${tree}`);
    console.log(`Expected Tree Height:\n${expected}`);

  })(Bst, BstNode);

})();

max-depth-binary-tree.js

(() => {

  class Bst {
    treeHeight(root) {
      if (root == null) return 0;
      return (
        (left, right) =>
          Math.max(this.treeHeight(left), this.treeHeight(right))
      )(
        root.left, root.right
      )
        + 1;
    }
  }

  class BstNode {
    constructor(data = null) {
      this.data = data;
      this.right = null;
      this.left = null;
    }
  }

  // builder - main function
  (function main(bst, bstNode) {
    let expected = 5;
    let root = new bstNode(5);
    root.left = new bstNode(10);
    root.left.right = new bstNode(25);
    root.left.right.right = new bstNode(35);
    root.left.right.left = new bstNode(30);
    root.left.right.left.left = new bstNode(20);
    root.right = new bstNode(15);

    let tree = (new bst().treeHeight(root));

    console.log(`Binary Tree has a height of: ${tree}`);
    console.log(`Expected Tree Height:\n${expected}`);

  })(Bst, BstNode);

})();