leetcode

commit 3002d395e054d76524902e489fd38b32f9e0a704
parent cde9bd2098ed0a590271b4e26de48029677ff5ea
Author: Jack Sangdahl <jack@pngu.org>
Date:   Mon, 23 Feb 2026 19:20:23 -0700

1022. sum of root to leaf binary numbers

Diffstat:
A
sum_root_leaf_binary_num.c
 | 
35
+++++++++++++++++++++++++++++++++++
A
sum_root_leaf_binary_num.py
 | 
34
++++++++++++++++++++++++++++++++++

2 files changed, 69 insertions(+), 0 deletions(-)
diff --git a/sum_root_leaf_binary_num.c b/sum_root_leaf_binary_num.c
@@ -0,0 +1,35 @@
+// 1022. Sum of Root To Leaf Binary Numbers
+#include "leetcode.h"
+
+/*
+ * you are given the 'root' of a binary tree where each node has a value of 0
+ * or 1. each root to leaf path represents a binary number starting with the
+ * most significant bit. for all leaves in the tree, consider the numbers
+ * represented by the path from the root to that leaf. return the  sum of these
+ * numbers. the test cases are generated such that the answer fits in a 32-bit
+ * integer.
+ */
+
+int dfs(struct TreeNode *root, int val) {
+  if (!root)
+    return 0;
+  val = (val << 1) | root->val;
+  int sum = dfs(root->left, val) + dfs(root->right, val);
+  return (val & -!sum) | sum;
+}
+
+int sumRootToLeaf(struct TreeNode *root) { return dfs(root, 0); }
+
+int main() {
+  int r1i[] = {1, 0, 1, 0, 1, 0, 1}, r2i[] = {0};
+  struct TreeNode *r1 = treenode_build(r1i, ARRAY_SIZE(r1i));
+  struct TreeNode *r2 = treenode_build(r2i, ARRAY_SIZE(r2i));
+  int srtl1 = sumRootToLeaf(r1);
+  int srtl2 = sumRootToLeaf(r2);
+  printf("%d\n", srtl1); // expect: 22
+  assert(srtl1 == 22);
+  printf("%d\n", srtl2); // expect: 0
+  assert(srtl2 == 0);
+  treenode_free(r1);
+  treenode_free(r2);
+}
diff --git a/sum_root_leaf_binary_num.py b/sum_root_leaf_binary_num.py
@@ -0,0 +1,34 @@
+# 1022. Sum of Root To Leaf Binary Numbers
+from typing import Optional
+
+from leetcode import TreeNode, treenode_build
+
+"""
+you are given the 'root' of a binary tree where each node has a value of 0
+or 1. each root to leaf path represents a binary number starting with the
+most significant bit. for all leaves in the tree, consider the numbers
+represented by the path from the root to that leaf. return the  sum of these
+numbers. the test cases are generated such that the answer fits in a 32-bit
+integer.
+"""
+
+
+class Solution:
+    def sumRootToLeaf(self, root: Optional[TreeNode]) -> int:
+        def dfs(node, val):
+            if not root:
+                return 0
+            val = (val << 1) + node.val
+            if not node.left and not node.right:
+                return val
+            return dfs(node.left, val) + dfs(node.right, val)
+
+        return dfs(root, 0)
+
+
+if __name__ == "__main__":
+    obj = Solution()
+    r1 = treenode_build(vals=[1, 0, 1, 0, 1, 0, 1])
+    r2 = treenode_build(vals=[0])
+    print(obj.sumRootToLeaf(r1))
+    print(obj.sumRootToLeaf(r2))