2025 December 6 Problems

[daryl...@gmail.com]

Feel free to work on any of the problems you want; we'll have people present their solutions at 11:30.

Please post your solutions to this thread so others can use this as a reference.

1022. Sum of Root To Leaf Binary Numbers Easy 73.6%

3558. Number of Ways to Assign Edge Weights I Medium 53.3%

3559. Number of Ways to Assign Edge Weights II Hard 59.9%

We're going to try to use the same Google meet link as the last few times: https://meet.google.com/xnn-kifj-jnx?pli=1

[Lyne Tchapmi]

class Solution:

def sumRootToLeaf(self, root: Optional[TreeNode]) -> int:

# DFS with stack storing (node, prefix)

# For each node, mark node as visited, visit left, then right child

# When a leaf is reached, add leaf binary number to result

stack = [(root, str(root.val))]

result = 0

while stack:

node, prefix = stack.pop()

has_left = False

has_right = False

if not hasattr(node, 'visited'):

node.visited = True

if hasattr(node, 'left') and node.left:

stack.append((node.left, prefix + str(node.left.val)))

has_left = True

if hasattr(node, 'right') and node.right:

stack.append((node.right, prefix + str(node.right.val)))

has_right = True

if not (has_left or has_right): # Leaf node

result += int(prefix, 2)

return result

[Anuj Patnaik]

# Definition for a binary tree node.

# class TreeNode:

# def __init__(self, val=0, left=None, right=None):

# self.val = val

# self.left = left

# self.right = right

class Solution:

def sumRootToLeaf(self, root: Optional[TreeNode]) -> int:

stack = [(root, 0)]

total = 0

while len(stack) > 0:

curr = stack.pop()

node = curr[0]

value = 2 * curr[1] + node.val

if node.right != None:

stack.append((node.right, value))

if node.left != None:

stack.append((node.left, value))

if node.left == None and node.right == None:

total += value

return total

[Anuj Patnaik]

# Definition for a binary tree node.

# class TreeNode:

# def __init__(self, val=0, left=None, right=None):

# self.val = val

# self.left = left

# self.right = right

class Solution:

def sumRootToLeaf(self, root: Optional[TreeNode]) -> int:

stack = [(root, str(root.val))]

total = 0

while len(stack) > 0:

curr = stack.pop()

node = curr[0]

val = curr[1]

if node.right != None:

stack.append((node.right, val + str(node.right.val)))

if node.left != None:

stack.append((node.left, val + str(node.left.val)))

if node.left == None and node.right == None:

total += Solution.binary_2_int(val)

return total

def binary_2_int(b):

total_sum = 0

i = 0

while i < len(b):

total_sum += int(b[i]) * (2**(len(b) - i - 1))

i += 1

return total_sum

[FloM]

1022. Sum of Root To Leaf Binary Numbers Easy 73.6%

Time: O(n) Mem: O(n). n is number of nodes. 

class Solution {

public:

void dfs(TreeNode* node, int num, int& sum)

{

num *= 2;

num += node->val;

if (node->left == nullptr && node->right == nullptr)

{

sum += num;

return;

}

if (node->left != nullptr)

{

dfs(node->left, num, sum);

}

if (node->right != nullptr)

{

dfs(node->right, num, sum);

}

}

int sumRootToLeaf(TreeNode* root) {

int sum = 0;

dfs(root, 0, sum);

return sum;

}

};

On Saturday, December 6, 2025 at 10:32:23 AM UTC-8 Lyne Tchapmi wrote:

[FloM]

Library internet is working again!

[Anuj Patnaik]

class Solution:

def assignEdgeWeights(self, edges: List[List[int]]) -> int:

depth = {1: 0}

max_depth = 0

while len(depth) < len(edges) + 1:

for i in edges:

if i[0] in depth and i[1] not in depth:

depth[i[1]] = depth[i[0]] + 1

max_depth = max(max_depth,depth[i[1]])

elif i[1] in depth and i[0] not in depth:

depth[i[0]] = depth[i[1]] + 1

max_depth = max(max_depth,depth[i[0]])

return (2 ** (max_depth - 1)) % (10**9 + 7)

[Allen S.]

/**

* Definition for a binary tree node.

* type TreeNode struct {

* Val int

* Left *TreeNode

* Right *TreeNode

* }

*/

func sumRootToLeaf(root *TreeNode) int {

res := 0

var dfs func(root *TreeNode, num int)

dfs = func(root *TreeNode, num int) {

if root == nil {

return

}

num = num * 2 + root.Val

if root.Left == nil && root.Right == nil {

res += num

return

}

dfs(root.Left, num)

dfs(root.Right, num)

}

dfs(root, 0)

return res

}

On Saturday, December 6, 2025 at 9:40:26 AM UTC-8 daryl...@gmail.com wrote:

[Wang Lijun]

class Solution:

def sumRootToLeaf(self, root: Optional[TreeNode]) -> int:

def dfs(root, total):

if not root:

return 0

total = root.val + total * 2

if not root.left and not root.right:

return total

return dfs(root.left, total) + dfs(root.right, total)

return dfs(root, 0)

On Saturday, December 6, 2025 at 10:35:43 AM UTC-8 FloM wrote:

[Lyne Tchapmi]

from collections import defaultdict, deque

import math

class Graph:

def __init__(self, edges):

self.nodes = defaultdict(set)

self.__edges_to_graph(edges)

def __edges_to_graph(self, edges):

for edge in edges:

u, v = edge

self.nodes[u].add(v)

self.nodes[v].add(u)

def get_max_depth(self):

stack = deque([(1, 0)])

visited = {}

max_depth = 0

while stack:

node, depth = stack.pop()

if node not in visited:

visited[node] = True

max_depth = max(depth, max_depth)

for child in self.nodes[node]:

if child not in visited:

stack.append((child, depth + 1))

return max_depth

class Solution:

def assignEdgeWeights(self, edges: List[List[int]]) -> int:

modulo = 10**9 + 7

graph = Graph(edges)

D = graph.get_max_depth()

# Slow solution

# assignments = 0

# for K in range(1, D + 1, 2):

# assignments += math.comb(D, K)

# assignments %= modulo

# return assignments

return pow(2, D -1, modulo)

[Allen S.]

func assignEdgeWeights(edges [][]int) int {

// get tree depth - d, that is the exponent

// 2^d / 2 == 2^(d-1)

t := make(map[int][]int, len(edges))

for _, e := range edges {

t[e[0]] = append(t[e[0]], e[1])

t[e[1]] = append(t[e[1]], e[0])

}

seen := make(map[int]bool)

maxDepth := 0

stack := [][]int{{1,0}} // node value and the node count

for len(stack) > 0 {

top := len(stack) - 1

now := stack[top]

stack = stack[:top] // pop

value := now[0]

seen[value] = true

count := now[1]

maxDepth = max(maxDepth, count)

for _, nei := range t[value] {

if !seen[nei] {

stack = append(stack, []int{nei, count+1})

}

}

}

res := 1

for range maxDepth {

res = res % (1e9 + 7)

res = res * 2

}

return res / 2

}

On Saturday, December 6, 2025 at 9:40:26 AM UTC-8 daryl...@gmail.com wrote:

[Gowrima Jayaramu]

# Definition for a binary tree node.

# class TreeNode:

# def __init__(self, val=0, left=None, right=None):

# self.val = val

# self.left = left

# self.right = right

class Solution:

def sumRootToLeaf(self, root: Optional["TreeNode"]) -> int:

def dfs(node, cur):

if not node:

return 0

cur = (cur << 1) | node.val

if not node.left and not node.right:

return cur

return dfs(node.left, cur) + dfs(node.right, cur)

return dfs(root, 0)

[Carlos Green]

/**

* Definition for a binary tree node.

* class TreeNode {

* val: number

* left: TreeNode | null

* right: TreeNode | null

* constructor(val?: number, left?: TreeNode | null, right?: TreeNode | null) {

* this.val = (val===undefined ? 0 : val)

* this.left = (left===undefined ? null : left)

* this.right = (right===undefined ? null : right)

* }

* }

*/

function sumRootToLeaf(root: TreeNode | null): number {

if (!root) return 0

const paths: string[] = []

const dfs = (node: TreeNode | null, path: string=''):void => {

if (!node) return

if (node.left === null && node.right === null) {

path += node.val

paths.push(path)

}

path += node.val

dfs(node.left, path)

dfs(node.right, path)

}

dfs(root)

return paths.reduce((a,c) => a += parseInt(c, 2), 0)

};

[Lyne Tchapmi]

Adaptation of Weights I to Weight II

from collections import defaultdict, deque

import math

class Graph:

def __init__(self, edges):

self.nodes = defaultdict(set)

self.__edges_to_graph(edges)

def __edges_to_graph(self, edges):

for edge in edges:

u, v = edge

self.nodes[u].add(v)

self.nodes[v].add(u)

def get_u_v_distance(self, query):

u, v = query

stack = deque([(u, 0)])

visited = {}

max_depth = 0

while stack:

node, depth = stack.pop()

if node == v:

return depth

if node not in visited:

visited[node] = True

max_depth = max(depth, max_depth)

for child in self.nodes[node]:

if child not in visited:

stack.append((child, depth + 1))

return max_depth

class Solution:

def assignEdgeWeights(self, edges: List[List[int]], queries: List[List[int]]) -> List[int]:

result = []

graph = Graph(edges)

modulo = 10**9 + 7

for query in queries:

D = graph.get_u_v_distance(query)

if D == 0:

result.append(0)

else:

result.append(pow(2, D-1, modulo))

return result