Sum of all left leaves

Problem: Find the sum of all left leaves in a given binary tree.

Example:

    1
   / \
  2   3
    /  \
   4    5

There are two left leaves in the binary tree, with values 2 and 4 respectively. Return 6.

Approach: A simple preorder traversal will work here.

Implementation in C#:

        public int SumOfLeftLeaves()

        {

            if (this.Root == null)

            {

                return 0;

            }

            return this.SumOfLeftLeaves(this.Root);

        }

        private int SumOfLeftLeaves(BinaryTreeNode node)

        {

            if (node == null)

            {

                return 0;

            }

            int leftSum = 0, rightSum = 0;

            if (node.LeftNode != null)

            {

                leftSum = this.SumOfLeftLeaves(node.LeftNode);

                if (node.LeftNode.LeftNode == null && node.LeftNode.RightNode == null)

                {

                    leftSum += node.LeftNode.Value;

                }

            }

            if (node.RightNode != null)

            {

                rightSum = this.SumOfLeftLeaves(node.RightNode);

            }

            return leftSum + rightSum;

        }

Complexity: O(n)