# #2 [Node Depths](https://www.algoexpert.io/questions/node-depths)

###### tags:`Binary tree` `Recursion` `Iteration`

## Issue

The distance between a node in a Binary Tree and the tree's root is called the node's depth.
Write a function that takes in a Binary Tree and returns the sum of its nodes' depths.
Each `BinaryTree` node has an integer `value`, a `left` child node, and a `right` child node. Children nodes can either be `BinaryTree` nodes themselves or `None` / `null`.

### Sample Input

tree =    1
       /     \
      2       3
    /   \   /   \
   4     5 6     7
 /   \
8     9

### Sample Output

16
// The depth of the node with value 2 is 1.
// The depth of the node with value 3 is 1.
// The depth of the node with value 4 is 2.
// The depth of the node with value 5 is 2.
// Etc..
// Summing all of these depths yields 16.

<br>

:::spoiler Time & Space complexity

Average case: when the tree is balanced

`O(n)` time | `O(h)` space - where `n` is the number of nodes in the Binary Tree and `h` is the height of the Binary Tree
:::

<br>

## Solutions

### Official

:::spoiler Recrusion

// Copyright © 2022 AlgoExpert LLC. All rights reserved.
// Average case: when the tree is balanced
// O(n) time | O(h) space - where n is the number of nodes in
// the Binary Tree and h is the height of the Binary Tree
function nodeDepths(root, depth = 0) {
  if (root === null) return 0;
  return depth + nodeDepths(root.left, depth + 1) + nodeDepths(root.right, depth + 1);
}

:::

<br>

:::spoiler Iteration

// Copyright © 2022 AlgoExpert LLC. All rights reserved.
// Average case: when the tree is balanced
// O(n) time | O(h) space - where n is the number of nodes in
// the Binary Tree and h is the height of the Binary Tree
function nodeDepths(root) {
  let sumOfDepths = 0;
  const stack = [{node: root, depth: 0}];
  while (stack.length > 0) {
    const {node, depth} = stack.pop();
    if (node === null) continue;
    sumOfDepths += depth;
    stack.push({node: node.left, depth: depth + 1});
    stack.push({node: node.right, depth: depth + 1});
  }
  return sumOfDepths;
}

:::

<br>

### Everyone's

:::spoiler Hao

/**
 * Time complexity: O(n) where n stands for numbers of nodes in the tree
 * Space complexity: O(m) where m stands for the deepest level of the tree
 */

function nodeDepths(root) {
  let sum = 0;
  const nodeDepthsInner = (node, curDepth) => {
    sum += curDepth;
    if (node.left !== null) nodeDepthsInner(node.left, curDepth + 1);
    if (node.right !== null) nodeDepthsInner(node.right, curDepth + 1);
  };
  nodeDepthsInner(root, 0);
  return sum;
}

:::

<br>

:::spoiler YC

/*
	time: O(n); - where n is the number of nodes in the tree
	space: O(h); - where h is the height of the tree
*/

function nodeDepths(root) {
  return add(root, 0);
}

function add(node, depth){
  if(!node) return 0;
  return depth + add(node.left, depth + 1) + add(node.right, depth + 1);
}

:::

<br>

:::spoiler 月薪

// Time: O(n) Space O(n), n is the length of nodes
function nodeDepths(root, deep = 0, deepSums = []) {
  deepSums.push(deep);
  if(root.right){
    nodeDepths(root.right, deep + 1, deepSums);
  }
  if(root.left){
    nodeDepths(root.left, deep + 1, deepSums);
  }
  return deepSums.reduce((a,b) => a + b)
}

:::

<br>

:::spoiler 東

/*
Time O(n) | Space O(c)
where n is the number of nodes in the tree,
c is the maximun depth of the tree
*/

function nodeDepths(root) {
  let depthSum = 0;
  let currDepth = 0;
  function calcDepth(node){ 
    if(node.left) {
      currDepth++;
      calcDepth(node.left);
    }
    if(node.right){
      currDepth++;
      calcDepth(node.right)
    }
    depthSum += currDepth;
    currDepth --;
  }
  calcDepth(root);
  return depthSum;
}

:::

<br>

## Supplement
### DFS：優先走遍距離起點最遠之處
> 1. 通常都用遞迴來實作
> 2. 習慣上會把map、visited（紀錄有沒有被走過的）、以及其他相關資訊放到global變數，讓遞迴能夠存取。


### BFS：將同一層的所有節點走完，才會走向下一層
> 用 Queue 來輔助


### unbalanced tree