Sum of Even Nodes on a Path in a Numbered Binary Tree
Problem statement
An endless full binary tree is numbered level by level from left to right, starting with 0 at the root. Node p has children 2p + 1 and 2p + 2, so the parent of every node p > 0 is (p - 1) / 2, rounded down. Each node's value is its number.
Given two nodes a and b, return the sum of the even values on the path between them. The path includes both a and b, and every node on it is counted once. If a == b, the path is just that node.
Function
sumEvenNodesOnPath(a: int, b: int) → longExamples
Example 1
a = 7b = 4return = 4The parent of 7 is 3, and the parent of 3 is 1. Node 1 is also the parent of 4, so the path is 7 → 3 → 1 → 4. The only even value on it is 4.
Example 2
a = 5b = 6return = 8Nodes 5 and 6 share the parent 2. The path is 5 → 2 → 6, and the even values are 2 and 6, so the sum is 8.
Example 3
a = 0b = 13return = 8Going up from 13 gives 6, then 2, then the root 0. The path is 0 → 2 → 6 → 13, and the even values add up to 0 + 2 + 6 = 8.
Example 4
a = 10b = 10return = 10Both ends are the same node, so the path is just node 10. It is even, so the answer is 10.
Constraints
0 <= a, b <= 10^9