Sum of Roots
Easy
Given a binary search tree (BST), return the sum of the values of all roots which have at least one child node. In a BST, the left child contains only nodes with values less than the parent node's value, and the right child only nodes with values greater than the parent node.
Example 1
Input
[ { "value": 10, "left": { "value": 5, "left": null, "right": null }, "right": { "value": 15, "left": null, "right": null } } ]
Output
10
Explanation. The root has children, hence it's included in the sum.
Example 2
Input
[ { "value": 20, "left": { "value": 10, "left": { "value": 5, "left": null, "right": null }, "right": { "value": 15, "left": null, "right": null } }, "right": { "value": 30, "left": null, "right": null } } ]
Output
30
Explanation. The node with value 20 and 10 have children, so their sum is 30.
Example 3
Input
[ { "value": 40, "left": null, "right": null } ]
Output
0
Explanation. The root has no children so it's not included in the sum.
Follow-up: Can you solve the problem with O(n) complexity in terms of both time and space?
Constraints:
The BST will have at least one node and at most 10,000 nodes. All values in the tree will be integer values.
- Views
- 13