Sum of left children — Preorder traversal


Sum of Left Leaves

Easy :

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


Iterative Code:

Recursive Code:

Complexity Analysis

Let N be the number of nodes.

Time complexity : O(N)

  • The code within the recursive function is all O(1). The function is called exactly once for each of the N nodes. Therefore, the total time complexity of the algorithm is O(N).

Space complexity : O(N)

  • In the worst case, the tree consists of nodes that form a single deep strand. In this case, the runtime-stack will have NN calls to preorder(...) on it at the same time, giving a worst-case space complexity of O(N).

Currently preparing for interviews

Get the Medium app

A button that says 'Download on the App Store', and if clicked it will lead you to the iOS App store
A button that says 'Get it on, Google Play', and if clicked it will lead you to the Google Play store