Calculate sum of root to leaf digits in a binary tree
Given a binary tree, where each node stores a value between 0 and 9, calculate the sum of the numbers created by the paths from root to leaf.
For example,
Input: Binary Tree
1
/ \
2 3
/ \
4 5
Output: 262
Explanation: Three root-to-leaf paths exist, and they are as follows:
[1 -> 2 -> 4]
[1 -> 2 -> 5]
[1 -> 3]
They represent the numbers 124, 125, and 13, respectively. They add up to 124 + 123 + 13 to make 262.
1
/ \
2 3
/ \
4 5
Output: 262
Explanation: Three root-to-leaf paths exist, and they are as follows:
[1 -> 2 -> 4]
[1 -> 2 -> 5]
[1 -> 3]
They represent the numbers 124, 125, and 13, respectively. They add up to 124 + 123 + 13 to make 262.
1. Recursive Solution
We can use recursion to solve the problem. The idea is to traverse the tree in a preorder fashion and construct the sum for each root-to-leaf path, as we go from top to bottom. Following is the C++, Java, and Python implementation based on the idea:
C++
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 |
#include <iostream> using namespace std; // Data structure to store a binary tree node struct Node { int data; Node *left, *right; Node(int data) { this->data = data; this->left = this->right = nullptr; } }; // Recursive function to calculate the sum of numbers formed by the root-to-leaf paths int findSum(Node* root, int sum) { // base case: sum is 0 for an empty tree if (!root) { return 0; } // add the value of the current node to the sum sum = sum * 10 + root->data; // return the sum if the current node is a leaf node if (!root->left && !root->right) { return sum; } // recur and return the sum of the left and right subtrees return findSum(root->left, sum) + findSum(root->right, sum); } // Function to calculate sum of numbers formed by the root-to-leaf paths int findRootToLeafPathsSum(Node* root) { return findSum(root, 0); } int main() { /* Construct the following tree 1 / \ 2 3 / \ 4 5 */ Node* root = new Node(1); root->left = new Node(2); root->right = new Node(3); root->left->left = new Node(4); root->left->right = new Node(5); cout << findRootToLeafPathsSum(root); return 0; } |
Output:
262
Java
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 |
// A class to store a binary tree node class Node { int data; Node left = null, right = null; Node(int data) { this.data = data; } } class Main { // Recursive function to calculate the sum of numbers formed by the root-to-leaf paths public static int findSum(Node root, int sum) { // base case: sum is 0 for an empty tree if (root == null) { return 0; } // add the value of the current node to the sum sum = sum * 10 + root.data; // return the sum if the current node is a leaf node if (root.left == null && root.right == null) { return sum; } // recur and return the sum of the left and right subtrees return findSum(root.left, sum) + findSum(root.right, sum); } public static int findRootToLeafPathsSum(Node root) { return findSum(root, 0); } public static void main(String[] args) { /* Construct the following tree 1 / \ 2 3 / \ 4 5 */ Node root = new Node(1); root.left = new Node(2); root.right = new Node(3); root.left.left = new Node(4); root.left.right = new Node(5); System.out.println(findRootToLeafPathsSum(root)); } } |
Output:
262
Python
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 |
# A class to store a binary tree node class Node: def __init__(self, data=None, left=None, right=None): self.data = data self.left = left self.right = right # Recursive function to calculate the sum of numbers formed by the root-to-leaf paths def findSum(root, sum): # base case: for an empty tree, the sum is 0 if root is None: return 0 # add the value of the current node to the sum sum = sum * 10 + root.data # return the sum if the current node is a leaf node if root.left is None and root.right is None: return sum # recur and return the sum of the left and right subtrees return findSum(root.left, sum) + findSum(root.right, sum) def findRootToLeafPathsSum(root): return findSum(root, 0) if __name__ == '__main__': ''' Construct the following tree 1 / \ 2 3 / \ 4 5 ''' root = Node(1) root.left = Node(2) root.right = Node(3) root.left.left = Node(4) root.left.right = Node(5) print(findRootToLeafPathsSum(root)) |
Output:
262
The above recursive answer has an O(n) time complexity, where n is the total number of nodes in the binary tree. The program needs O(h) auxiliary space for the call stack, where ‘h’ is the height of the tree.
2. Iterative Solution
In an iterative version, we can traverse the tree in level order, and while doing so, we update the data of every encountered node with the sum of the paths so far. Now, if a leaf node is encountered, we can easily add the root-to-leaf path sum to the result, as demonstrated below in C++, Java, and Python. Keep in mind that this solution changes the binary tree nodes’ values. This can be avoided by making a copy of the child nodes and enqueuing them after updating their data.
C++
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 |
#include <iostream> #include <queue> using namespace std; // Data structure to store a binary tree node struct Node { int data; Node *left, *right; Node(int data) { this->data = data; this->left = this->right = nullptr; } }; // Iterative function to calculate the sum of numbers formed by the root-to-leaf paths int findRootToLeafPathsSum(Node* root) { // base case if (root == nullptr) { return 0; } int sum = 0; // create an empty queue and enqueue the root node queue<Node*> q; q.push(root); // loop until the queue is empty while (!q.empty()) { // dequeue the next node from the queue Node* curr = q.front(); q.pop(); // if the left child exists, enqueue it after updating its data with the // sum of path so far if (curr->left) { curr->left->data = curr->data * 10 + curr->left->data; q.push(curr->left); } // if the right child exists, enqueue it after updating its data with the // sum of path so far if (curr->right) { curr->right->data = curr->data * 10 + curr->right->data; q.push(curr->right); } // if we encountered a leaf node, add the node's data to the result if (curr->left == nullptr && curr->right == nullptr) { sum += curr->data; } } return sum; } int main() { /* Construct the following tree 1 / \ 2 3 / \ 4 5 */ Node* root = new Node(1); root->left = new Node(2); root->right = new Node(3); root->left->left = new Node(4); root->left->right = new Node(5); cout << findRootToLeafPathsSum(root); return 0; } |
Output:
262
Java
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 |
import java.util.ArrayDeque; import java.util.Deque; import java.util.Queue; // A class to store a binary tree node class Node { int data; Node left = null, right = null; Node(int data) { this.data = data; } } class Main { // Iterative function to calculate the sum of numbers formed by the root-to-leaf paths public static int findRootToLeafPathsSum(Node root) { // base case if (root == null) { return 0; } int sum = 0; // create an empty queue and enqueue the root node Queue<Node> queue = new ArrayDeque<>(); queue.add(root); // loop until the queue is empty while (!queue.isEmpty()) { // dequeue the next node from the queue Node curr = queue.poll(); // if the left child exists, enqueue it after updating its data with the // sum of path so far if (curr.left != null) { curr.left.data = curr.data * 10 + curr.left.data; queue.add(curr.left); } // if the right child exists, enqueue it after updating its data with the // sum of path so far if (curr.right != null) { curr.right.data = curr.data * 10 + curr.right.data; queue.add(curr.right); } // if we encountered a leaf node, add the node's data to the result if (curr.left == null && curr.right == null) { sum += curr.data; } } return sum; } public static void main(String[] args) { /* Construct the following tree 1 / \ 2 3 / \ 4 5 */ Node root = new Node(1); root.left = new Node(2); root.right = new Node(3); root.left.left = new Node(4); root.left.right = new Node(5); System.out.println(findRootToLeafPathsSum(root)); } } |
Output:
262
Python
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 |
from collections import deque # A class to store a binary tree node class Node: def __init__(self, data=None, left=None, right=None): self.data = data self.left = left self.right = right # Iterative function to calculate the sum of numbers formed by the root-to-leaf paths def findRootToLeafPathsSum(root): # base case if root is None: return 0 sum = 0 # create an empty queue and enqueue the root node q = deque() q.append(root) # loop until the queue is empty while q: # dequeue the next node from the queue curr = q.pop() # if the left child exists, enqueue it after updating its data with the # sum of path so far if curr.left: curr.left.data = curr.data * 10 + curr.left.data q.append(curr.left) # if the right child exists, enqueue it after updating its data with the # sum of path so far if curr.right: curr.right.data = curr.data * 10 + curr.right.data q.append(curr.right) # if we encountered a leaf node, add the node's data to the result if curr.left is None and curr.right is None: sum += curr.data return sum if __name__ == '__main__': ''' Construct the following tree 1 / \ 2 3 / \ 4 5 ''' root = Node(1) root.left = Node(2) root.right = Node(3) root.left.left = Node(4) root.left.right = Node(5) print(findRootToLeafPathsSum(root)) |
Output:
262
The above iterative method has O(n) time complexity, where n is the total number of nodes in the binary tree. The program needs O(n) auxiliary space for the queue data structure.
Also See:
Thanks for reading.
To share your code in the comments, please use our online compiler that supports C, C++, Java, Python, JavaScript, C#, PHP, and many more popular programming languages.
Like us? Refer us to your friends and support our growth. Happy coding :)