<jupyter_start><jupyter_text>All Kinds Of Node Depths[link](https://www.algoexpert.io/questions/All%20Kinds%20Of%20Node%20Depths)<jupyter_code>def allKindsOfNodeDepths(root):
    # Write your code here.
    pass


# This is the class of the input binary tree.
class BinaryTree:
    def __init__(self, value):
        self.value = value
        self.left = None
        self.right = None<jupyter_output><empty_output><jupyter_text>My Solution<jupyter_code>def allKindsOfNodeDepths(root):
    # Write your code here.
    totalSum = [0]
    depthsSum, _ = getDepthsSum(root, totalSum)
    return totalSum[0]

def getDepthsSum(node, totalSum):
    if node is None:
        return 0, 0
    
    leftDepthsSum, leftNumOfNodes = getDepthsSum(node.left, totalSum)
    rightDepthsSum, rightNumOfNodes = getDepthsSum(node.right, totalSum)
    
    depthsSum = leftDepthsSum + leftNumOfNodes + rightDepthsSum + rightNumOfNodes
    numOfNodes = leftNumOfNodes + rightNumOfNodes + 1
    totalSum[0] += depthsSum
    
    return depthsSum, numOfNodes


# This is the class of the input binary tree.
class BinaryTree:
    def __init__(self, value):
        self.value = value
        self.left = None
        self.right = None
def allKindsOfNodeDepths(root):
    # Write your code here.
    return getDepthsSum(root)[2]

def getDepthsSum(node):
    if node is None:
        return 0, 0, 0
    
    leftDepthsSum, leftNumOfNodes, leftTotalSum = getDepthsSum(node.left)
    rightDepthsSum, rightNumOfNodes, rightTotalSum = getDepthsSum(node.right)
    
    depthsSum = leftDepthsSum + leftNumOfNodes + rightDepthsSum + rightNumOfNodes
    numOfNodes = leftNumOfNodes + rightNumOfNodes + 1
    totalSum = depthsSum + leftTotalSum + rightTotalSum
    
    return depthsSum, numOfNodes, totalSum


# This is the class of the input binary tree.
class BinaryTree:
    def __init__(self, value):
        self.value = value
        self.left = None
        self.right = None<jupyter_output><empty_output><jupyter_text>Expert Solution<jupyter_code># iteratively
# Average case: when the tree is balanced
# O(nlog(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
def allKindsOfNodeDepths(root):
    sumOfAllDepths = 0
    stack = [root]
    while len(stack) > 0:
        node = stack.pop()
        if node is None:
            continue
        sumOfAllDepths += nodeDepths(node)
        stack.append(node.left)
        stack.append(node.right)
    return sumOfAllDepths

def nodeDepths(node, depth = 0):
    if node is None:
        return 0
    return depth + nodeDepths(node.left, depth + 1) + nodeDepths(node.right, depth + 1)

# This is the class of the input binary tree.
class BinaryTree:
    def __init__(self, value):
        self.value = value
        self.left = None
        self.right = None
# Recursively
# Average case: when the tree is balanced
# O(nlog(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
def allKindsOfNodeDepths(root):
    if root is None:
        return 0
    return allKindsOfNodeDepths(root.left) + allKindsOfNodeDepths(root.right) + nodeDepths(root)

def nodeDepths(node, depth = 0):
    if node is None:
        return 0
    return depth + nodeDepths(node.left, depth + 1) + nodeDepths(node.right, depth + 1)

# This is the class of the input binary tree.
class BinaryTree:
    def __init__(self, value):
        self.value = value
        self.left = None
        self.right = None
# Average case: when the tree is balanced
# O(n) time | O(n) space - where n is the number of nodes in the Binary Tree
def allKindsOfNodeDepths(root):
    nodeCounts = {}
    addNodeCounts(root, nodeCounts)
    nodeDepths = {}
    addNodeDepths(root, nodeDepths, NodeDepths)

def sumAllNodeDepths(node, nodeDepths):
    if node is None:
        return 0
    return sumAllNodeDepths(node.left, nodeDepths) + sumAllNodeDepths(node.right, nodeDepths) + nodeDepths[node]


def addNodeDepths(node, nodeDepths, nodeCounts):
    nodeDepths[node] = 0
    if node.left is not None:
        addNodeDepths(node.left, nodeDepths. nodeCounts)
        nodeDepths[node] += nodeDepths[node.left] + nodeCounts[node.left]
    if node.right is not None:
        addNodeDepths(node.right, nodeDepths, nodeCounts)
        nodeDepths[node] += nodeDepths[node.right] + nodeCounts[node.right]

def addNodeCounts(node, nodeCounts):
    nodeCounts[node] = 1
    if node.left is not None:
        addNodeCounts(node.left, nodeCounts)
        nodeCounts[node] += nodeCounts[node.left]
    if node.right is not None:
        addNodeCounts(node.right, nodeCounts)
        nodeCounts[node] += nodeCounts[node.right]


# This is the class of the input binary tree.
class BinaryTree:
    def __init__(self, value):
        self.value = value
        self.left = None
        self.right = None
# 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
def allKindsOfNodeDepths(root):
    return getTreeInfo(root).sumOfAllDepths


def getTreeInfo(tree):
    if tree is None:
        return TreeInfo(0, 0, 0)

    leftTreeInfo = getTreeInfo(tree.left)
    rightTreeInfo = getTreeInfo(tree.right)

    sumOfLeftDepths = leftTreeInfo.sumOfDepths + leftTreeInfo.numNodesInTree
    sumOfRightDepths = rightTreeInfo.sumOfDepths + rightTreeInfo.numNodesInTree

    numNodesInTree = 1 + leftTreeInfo.numNodesInTree + rightTreeInfo.numNodesInTree
    sumOfDepths = sumOfLeftDepths + sumOfRightDepths
    sumOfAllDepths = sumOfDepths + leftTreeInfo.sumOfAllDepths + rightTreeInfo.sumOfAllDepths

    return TreeInfo(numNodesInTree, sumOfDepths, sumOfAllDepths)


class TreeInfo:
    def __init__(self, numNodesInTree, sumOfDepths, sumOfAllDepths):
        self.numNodesInTree = numNodesInTree
        self.sumOfDepths = sumOfDepths
        self.sumOfAllDepths = sumOfAllDepths


# This is the class of the input binary tree.
class BinaryTree:
    def __init__(self, value):
        self.value = value
        self.left = None
        self.right = None<jupyter_output><empty_output><jupyter_text>There's an additional, cleaner and more clever way of solving this question with the same time and space time complexities as the optimal solution covered in the video explanation.Realize that a given node in the input tree has:- a depth of `1` with respect to its parent node- a depth of `2` with respect to its parent's parent node- a depth of `3` with respect to its parent's parent's node- ...- a depth of `d` with respect to the root nodeSince these depths are captured in each subtree's nodes' depths, which we sum up to get the final answer, we can deduce that each node in the input tree contributes `1 + 2 + 3 + ... + d - 1 + d` to the final answer.Thus, we can solve this question with a simple recursive function that takes in the running `depthSum` and adds the current node's depth to it at every call. See Solution 5 for the implementation of this algorithm.We can go one step further by realizing that the sum `1 + 2 + 3 + ... + n - 1 + n` can be calculated with the formula `(n * (n + 1)) / 2`, which eliminates the need to pass the running `depthSum` to each recursive function call. See Solution 6 for this implementation.<jupyter_code># 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
def allKindsOfNodeDepths(root, depthSum=0, depth=0):
    if root is None:
        return 0

    depthSum += depth
    return (
        depthSum
        + allKindsOfNodeDepths(root.left, depthSum, depth + 1)
        + allKindsOfNodeDepths(root.right, depthSum, depth + 1)
    )


# This is the class of the input binary tree.
class BinaryTree:
    def __init__(self, value):
        self.value = value
        self.left = None
        self.right = None
# 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
def allKindsOfNodeDepths(root, depth=0):
    if root is None:
        return 0

    # Formula to calculate 1 + 2 + 3 + ... + depth - 1 + depth
    depthSum = (depth * (depth + 1)) / 2
    return depthSum + allKindsOfNodeDepths(root.left, depth + 1) + allKindsOfNodeDepths(root.right, depth + 1)


# This is the class of the input binary tree.
class BinaryTree:
    def __init__(self, value):
        self.value = value
        self.left = None
        self.right = None<jupyter_output><empty_output>
{'fraction_non_alphanumeric': 0.08126017205301093, 'fraction_numerical': 0.007788886305510346, 'mean_word_length': 3.250494071146245, 'pattern_counts': {'":': 0, '<': 17, '<?xml version=': 0, '>': 18, 'https://': 1, 'lorem ipsum': 0, 'www.': 1, 'xml': 0}, 'pii_count': 0, 'substrings_counts': 0, 'word_list_counts': {'cursed_substrings.json': 0, 'profanity_word_list.json': 0, 'sexual_word_list.json': 0, 'zh_pornsignals.json': 0}}
{'chain_length': '4', 'dir': 'jupyter-structured-clean-dedup', 'id': '628261', 'license': 'MIT', 'n_tokens_mistral': 2780, 'n_tokens_neox': 2670, 'n_words': 909, 'path': 'algoExpert/all_kinds_of_node_depths/solution.ipynb', 'repo_name': 'maple1eaf/learning_algorithm', 'size': '8602'}