LeetCode: Sum of Left Leaves
This problem by LeetCode is a good candidate to exemplify a method to convert a recursive function to non-recursive one. Problem is this: https://leetcode.com/problems/sum-of-left-leaves/, or copied/pasted here: "Find the sum of all left leaves in a given binary tree.".
Recursively one can solve this problem easily in 3 lines of code:
public int SumOfLeftLeaves(TreeNode root)
{
if (root == null) return 0; //Line 1
if (root.left != null && root.left.left == null && root.left.right == null) return root.left.val + SumOfLeftLeaves(root.right); //Line 2
return SumOfLeftLeaves(root.left) + SumOfLeftLeaves(root.right); //Line 3
}
Cheers, and Merry Christmas!!!
Marcelo
Recursively one can solve this problem easily in 3 lines of code:
public int SumOfLeftLeaves(TreeNode root)
{
if (root == null) return 0; //Line 1
if (root.left != null && root.left.left == null && root.left.right == null) return root.left.val + SumOfLeftLeaves(root.right); //Line 2
return SumOfLeftLeaves(root.left) + SumOfLeftLeaves(root.right); //Line 3
}
In essence the first line is the base case (no tree, no sum), the second line is the processing on the current node (if the current node is a leaf and it is a left one, add it to the result) and finally the third line is the induction step (continue the procedure to all the other nodes in the tree).
The non-recursive version of this code is actually very similar logic-wise to the recursive one. First a Stack will be needed. Second, in order to facilitate the processing on the current node we'll be pushing to the stack the type of child node too ('n' none, 'l' left and 'r' right). Pushing and popping as we go until we have processed the entire tree (yes, still O(n)-time). A little more code, but avoiding the recursion traps:
public int SumOfLeftLeaves(TreeNode root)
{
if (root == null) return 0; //Base case
Stack<StackItem> stack = new Stack<StackItem>();
int sum = 0;
stack.Push(new StackItem(root, 'n'));
while (stack.Count > 0)
{
StackItem stackItem = stack.Pop();
if (stackItem.treeNode.left == null && stackItem.treeNode.right == null && stackItem.child == 'l') sum += stackItem.treeNode.val; //Processing
//Induction
if (stackItem.treeNode.left != null) stack.Push(new StackItem(stackItem.treeNode.left, 'l'));
if (stackItem.treeNode.right != null) stack.Push(new StackItem(stackItem.treeNode.right, 'r'));
}
return sum;
}
class StackItem
{
public TreeNode treeNode;
public char child;
public StackItem(TreeNode treeNode, char child)
{
this.treeNode = treeNode;
this.child = child;
}
}
Marcelo
ah, more classic :)
ReplyDeleteAnother easy imperative solution can use a queue, since traversal order does not matter here. Queue would be better for trees which are very deep and narrow, but stack is better for balanced or nearly balanced trees.
Current implementation can be improved a bit by getting rid of StackItem class, since it hurts performance - stack stores pointers to items, instead of pointers to nodes, so 2 dereferences are required instead of one. Your processing step already has enough information, so after getting rid of StackItem it can be changed to
if (treeNode.left != null && treeNode.left.left == null && treeNode.left.right == null) sum += treeNode.left.val; //Processing
My naive implementation looks as follows:
#include
class Solution {
public:
bool isLeaf(TreeNode* node) { return node->left == nullptr && node->right == nullptr;}
int sumOfLeftLeaves(TreeNode* root) {
if (root == nullptr) return 0;
int sum = 0;
stack s;
s.push(root);
while (!s.empty()) {
TreeNode * node = s.top(); s.pop();
if (node->left != nullptr && isLeaf(node->left)) sum += node->left->val;
if (node->left != nullptr) s.push(node->left);
if (node->right != nullptr) s.push(node->right);
}
return sum;
}
};
There is also a way which can potentially be more efficient, which uses an optimized traversal (a single push instead of 2).
#include
class Solution {
private:
bool isLeaf(const TreeNode* node) { return node->left == nullptr && node->right == nullptr; }
public:
int sumOfLeftLeaves(TreeNode* root) {
if (root == nullptr) return 0;
int sum = 0;
stack s;
TreeNode* node = root;
for (;;) {
if (node != nullptr) {
s.push(node);
node = node->left;
if (node != nullptr && isLeaf(node)) sum += node->val;
} else {
if (s.empty()) {
return sum;
} else {
node = s.top(); s.pop();
node = node->right;
}
}
}
return sum;
}
};
but due to extra branches its performance is not guaranteed to be better, so in practice I'd probably still stick with the simple solution above :)
Very nice!!! When I tried both the recursive and the non-recursive versions of my code they took exactly the same time, which was interesting. Thanks for the variants proposed!!!!
ReplyDelete