<jupyter_start><jupyter_text>Node Depths[link](https://www.algoexpert.io/questions/Node%20Depths)  My Solution<jupyter_code>def nodeDepths(root):
    # Write your code here.
    # nodesDepth needs O(n) space
    # recursive function calls needs O(n) stack space
    nodesDepth = nodeDepthTagger(root, 0, [])
    return sum(nodesDepth)
    
def nodeDepthTagger(node, depth, nodesDepth=[]):
    if node is not None:
        nodesDepth.append(depth)
        
        nodeDepthTagger(node.left, depth + 1, nodesDepth)
        nodeDepthTagger(node.right, depth + 1, nodesDepth)
    return nodesDepth

# 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 nodeDepths(root):
    # Write your code here.
    # depthSum needs O(1) space
    # recursive function calls needs O(n) stack space
    return nodeDepthTagger(root, 0, [0])
	
def nodeDepthTagger(node, depth, depthSum):
    # depthSum needs to be a referance, here I use a list
	if node is not None:
		depthSum[0] += depth
		
		nodeDepthTagger(node.left, depth + 1, depthSum)
		nodeDepthTagger(node.right, depth + 1, depthSum)
	return depthSum[0]


# 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>def nodeDepths(root, depth=0):
    """
    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
    """
    sumOfDepths = 0
    stack = [{'node': root, 'depth': 0}]
    while len(stack) > 0:
        nodeInfo = stack.pop()
        node, depth = nodeInfo['node'], nodeInfo['depth']
        if node is None:
            continue
        sumOfDepths += depth
        stack.append({'node': node.left, 'depth': depth + 1})
        stack.append({'node': node.right, 'depth': depth + 1})
    return sumOfDepths
# 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 nodeDepths(root, depth=0):
    """
    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
    """
    if root is None:
        return 0
    return depth + nodeDepths(root.left, depth+1) + nodeDepths(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.0998211091234347, 'fraction_numerical': 0.007871198568872988, 'mean_word_length': 2.8144611186903137, 'pattern_counts': {'":': 0, '<': 9, '<?xml version=': 0, '>': 10, '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': '2', 'dir': 'jupyter-structured-clean-dedup', 'id': '459223', 'license': 'MIT', 'n_tokens_mistral': 906, 'n_tokens_neox': 872, 'n_words': 293, 'path': 'algoExpert/node_depths/solution.ipynb', 'repo_name': 'maple1eaf/learning_algorithm', 'size': '2795'}