Sponsored
Sponsored
This approach involves using a recursive function to traverse the binary tree from the root to the leaves. During the traversal, we calculate the binary number formed by the path from the root to the current node, then sum up the numbers obtained when a leaf node is reached. The traversal is achieved using depth-first search (DFS).
Time Complexity: O(n), where n is the number of nodes in the tree because each node is visited once.
Space Complexity: O(h), where h is the height of the tree, due to the recursion stack. In the worst case, it could be O(n).
1#include <stdio.h>
2#include <stdlib.h>
3
4struct TreeNode {
5 int val;
6 struct TreeNode *left;
7 struct TreeNode *right;
8};
9
10int calculateSum(struct TreeNode* root, int currentSum) {
11 if (root == NULL) {
12 return 0;
13 }
14
15 currentSum = (currentSum << 1) | root->val;
16 if (root->left == NULL && root->right == NULL) {
17 return currentSum;
18 }
19 return calculateSum(root->left, currentSum) + calculateSum(root->right, currentSum);
20}
21
22int sumRootToLeaf(struct TreeNode* root) {
23 return calculateSum(root, 0);
24}This C solution defines a `TreeNode` structure for binary trees. The function `calculateSum` is recursive and is responsible for traversing the tree. It uses a `currentSum` variable that is left-shifted to build the binary number. When a leaf node is reached, it returns the binary-to-decimal converted number. Otherwise, it continues the DFS traversal.
This approach utilizes an iterative technique employing a stack to carry out a DFS. In each iteration, nodes are retrieved alongside their corresponding computed binary sum. This method is advantageous when stack overflow due to recursion is a concern, as it emulates recursion iteratively.
Time Complexity: O(n), due to visiting each node once.
Space Complexity: O(n), bounded by the stack's requirement to store node-state pairs.
1class TreeNode:
2 def
This Python implementation leverages a stack to perform iterative DFS. A tuple tracks each node alongside the current binary sum being accumulated. The process ensures all leaf nodes' paths are accounted for, computing a total sum iteratively.