Sum of Odd-Positioned BST Nodes

Problem Given a binary search tree, compute the sum of the values at the odd positions of a chosen traversal order — in-order or level-order — with position numbering starting at 1.

Input / Output

• Input: the root of a BST, plus which traversal order to use.
• Output: an integer — the sum of the values at positions 1, 3, 5, …

Constraints

• Up to ~10^5 nodes; values may be negative.
• Position means the index within the traversal sequence, not the node's depth — worth confirming, since "odd position" reads both ways.
• An empty tree returns 0.

Example

• In-order sequence [1,2,3,4,5,6,7] → odd positions 1st, 3rd, 5th, 7th → 1+3+5+7 = 16.
• Level-order over the same tree gives a different sequence and sum — the reason the traversal must be pinned down first.
• A single-node tree returns that node's value.