Sum of Roots

Binary Search TreeDepth-First SearchTree

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

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

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

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: 3