# Can you improve this algorithm?

• ``````/**
* Definition for binary tree
* public class TreeNode {
*     int val;
*     TreeNode left;
*     TreeNode right;
*     TreeNode(int x) { val = x; }
* }
*/
public class Solution {
public int sumNumbers(TreeNode root) {
if (root == null)
return 0;
return sumR(root, 0);
}
public int sumR(TreeNode root, int x) {
if (root.right == null && root.left == null)
return 10 * x + root.val;
int val = 0;
if (root.left != null)
val += sumR(root.left, 10 * x + root.val);
if (root.right != null)
val += sumR(root.right, 10 * x + root.val);
return val;
}
}``````

• This post is deleted!

• This post is deleted!

• I did it in almost the same way in C++ and I guess it cannot be optimized further. We have to visit each element once, atleast, and thats what our algorithm does.

Pasting my solution:

``````class Solution {
private:
void traverseAndSum(TreeNode *root, int &sum, int parSum);
public:
int sumNumbers(TreeNode *root) {
int sum = 0;
traverseAndSum(root, sum, 0);
return sum;
}
};

void Solution::traverseAndSum(TreeNode *root, int &sum, int parSum)
{
if (root == NULL)
return;

parSum = parSum * 10 + root->val;
if (root->left == NULL && root->right == NULL)
{
// Encountered a leaf node. Evaluate the sum
sum += parSum;
return;
}
traverseAndSum(root->left, sum, parSum);
traverseAndSum(root->right, sum, parSum);
}``````

• Same idea in iterative version.

``````int sumNumbers(TreeNode *root) {
int sum = 0;
if(root == NULL) return sum;
stack<TreeNode *> array;
stack<int> val;
array.push(root);
val.push(0);
while(!array.empty()){
TreeNode *node = array.top();
int prev = val.top();
array.pop();
val.pop();
while(node->left != NULL){
int cur = prev*10 + node->val;
if(node->right != NULL){
array.push(node->right);
val.push(cur);
}
prev = cur;
node = node->left;
}
int cur = prev*10 + node->val;
if(node->right == NULL){
sum += cur;
}else{
array.push(node->right);
val.push(cur);
}
}
return sum;
}``````

• I prefer the iterative method over recursion. I used 2 queues to do a breadth first traversal. both time and space complexity is O(N):

``````public class Solution {
public int sumNumbers(TreeNode root) {
int total = 0;
if(root !=null){
}
while(!q.isEmpty()){
TreeNode current = q.removeFirst();
int partialSum = sumq.removeFirst();
if(current.left == null && current.right==null){
total+=partialSum;
}else{
if(current.right !=null){
}
if(current.left !=null){
}

}

}
}
``````

}

• This post is deleted!

• This post is deleted!

class Solution {
public:
int sumNumbers(TreeNode *root)
{
if (!root)
return 0;

``````    vector<TreeNode*> sta;	// this is a vector to hold the nodes from root to a leaf. (Why not stack? Because when calculate the sum the vector is more easy than stack)
stack<bool> status;	// in PostOrder Traversal, the value of this stack represents the node whether should be pop.(false not pop, true pop)
TreeNode *top;
int temp, sum = 0;

while (root || !sta.empty())	// PostOrder Traversal
{
if (root)			// Node is non-empty push into vector, and push false in stack
{
sta.push_back(root);
status.push(false);
root = root->left;	// deep into left
}
else			// node is empty, consider whether the node should be pop
{
top = sta[sta.size() - 1]; // the top of the vector(equals to the top() function of stack STL)
if (!status.top())	   // if top of stack is fasle, change false to true, and change the node to the right
{
status.pop();
status.push(true);
root = top->right;
}
else			// the node should be pop
{
if (!top->left && !top->right)	// the node is a leaf,
{
temp = 0;
for (int i = 0; i < sta.size(); i++) 	// calculate the sum of vector (repersents the sum of root to this leaf)
temp = 10 * temp + sta[i]->val;
sum += temp;
}
sta.erase(sta.end() - 1);	// delete the "top one" of the vector
status.pop();
root = NULL;
}
}
}

return sum;
}
``````

};

• Hi @ikimk, thanks for your updating. Sorry to make this misunderstand. I mean it could be better to post this excellent code as an answer, not as a comment like what it is right now.

• ``````int sumNumbers(TreeNode *root) {
return sumNumber(root);
}

/*levelBase - holds number upto current level excluding nodes value.
For example, if the number upto current node is 1239, then levelBase will have 1230.*/
int sumNumber(TreeNode *root, int levelBase=0) {
if(root == 0)
return 0;
if(root->left == 0 && root->right == 0) {
return levelBase + root->val;
}
int nextLevelBase = (levelBase + root->val) *10 ;
int leftSubTreeSum = sumNumber(root->left, nextLevelBase);
int rightSubTreeSum = sumNumber(root->right, nextLevelBase);

return leftSubTreeSum + rightSubTreeSum;
}
``````

• We can do it without helper function.

``````class Solution:
# @param root, a tree node
# @return an integer
def sumNumbers(self, root):
if not root:
return 0
if not root.left and not root.right:
return root.val
val = 0
if root.left:
root.left.val += root.val * 10
val += self.sumNumbers(root.left)
root.left.val -= root.val * 10
if root.right:
root.right.val += root.val * 10
val += self.sumNumbers(root.right)
root.right.val -= root.val * 10
return val``````

• The reason you don't need helper function is that you change the node's value, which I think it's not a good way to solve this problem. It is better not change the input.

• My iterative solution, hope it's easy to understand. its space complexity is O(h), where h is the maximum height of the tree.

It traverse the tree in Post-Order. when traverse the tree, 'cur' point to the current node, 'pre' point to the last accessed node. There are only 3 cases: pre is cur's parent, pre is cur's left, child, pre is cur's right child.

for details, you can refer to http://leetcode.com/2010/10/binary-tree-post-order-traversal.html

``````int sumNumbers(TreeNode *root) {
if (root == nullptr){
return 0;
}

stack<TreeNode*> stk;
TreeNode* pre = nullptr;
stk.push(root);
int sum = 0;
int number = 0;

while (!stk.empty()){
TreeNode* cur = stk.top();

// we are traversing down the tree
if (!pre || (pre->left == cur) || (pre->right == cur)){
number = number * 10 + cur->val;
if (cur->left){
stk.push(cur->left);
}
else if (cur->right){
stk.push(cur->right);
}
else {
sum += number;
number /= 10;
stk.pop();
}
}
// we are traversing up the tree from the left
else if (cur->left == pre){
if (cur->right){
stk.push(cur->right);
}
else{
stk.pop();
number /= 10;
}
}
// we are traversing up the tree from the right
else{
stk.pop();
number /= 10;
}
pre = cur;
}

return sum;
}``````

• According to potpie, I have a very simple solution:

``````int sumNumbers(TreeNode *root) {
return sumNumbers_helper(root,0);
}
int sumNumbers_helper(TreeNode *root, int s) {
if (root == NULL) return 0; // root is NULL then return 0
s = s*10 + (root -> val);	// current sum times 10 plus root value
if (root->left == NULL && root->right == NULL) return s;	//both left and right are NULL, return sum
return sumNumbers_helper(root->left,s) + sumNumbers_helper(root->right,s); // recursively call the helper with sum
}
``````

• How about post order travel with two stack. It should be O(N) complicit and O(level of binary tree) space.

``````public int sumNumbers(TreeNode root) {
int result = 0;
if (root != null) {
Deque<Integer> dataStack = new ArrayDeque<>();
Deque<TreeNode> stack = new ArrayDeque<>();
TreeNode node = root;
TreeNode lastVisited = null;
while (!stack.isEmpty() || node != null) {
if (node != null) {
int t = dataStack.isEmpty() ? 0 : dataStack.peek();
t = t * 10 + node.val;
if (node.left == null && node.right == null) {
result += t;
}
stack.push(node);
dataStack.push(t);
node = node.left;
} else {
TreeNode peek = stack.peek();
if (peek.right != null && peek.right != lastVisited) {
node = peek.right;
} else {
stack.pop();
dataStack.pop();
lastVisited = peek;
}
}
}
}
return result;
}
``````

• I use this algorithm too.

• Thanks for sharing. Could you tell why you prefer iterative method?

• Hi ted7726,
I think you have the best solution with least number of lines of code possible. I wanted to give it a thumbs up or the vote but can't cause its already in a reply.. If you have posted it somewhere else, please do tell me, I will add my vote.
Thanks.

• Actually, your algorithm is depth-first-search, not breadth-first-search. For example, although root->right is pushed into stack right after root is visited, but it will be visited after root's whole left sub-tree is visited.

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.