FastPrepSum of Even Nodes on a Path in a Numbered Binary Tree
Problems/Sum of Even Nodes on a Path in a Numbered Binary Tree

Sum of Even Nodes on a Path in a Numbered Binary Tree

Adobe logoAdobe● MediumFULLTIMEPHONE SCREEN
QuestionFunctionExamplesConstraints

Problem statement

Source note: The interviewer asked: "Given Full binary tree with A, B. Find sum of even nodes on path from A to B." The candidate moved to a parent with p -> (p - 1)/2 and compared depths.

The report does not say how the nodes are numbered, whether the two end nodes count, or how large the numbers are. Here, nodes are numbered from 0 at the root, each node's value is its number, both end nodes are part of the path, and a and b are at most 10^9, so the sum can need 64 bits.

The judged task matches the report at about 85%.

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) → long

Examples

Example 1

a = 7b = 4return = 4

The 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 = 8

Nodes 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 = 8

Going 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 = 10

Both 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

More Adobe problems

  • Evaluate a Parenthesized Integer ExpressionPHONE SCREEN · Seen Oct 2026
  • All Elements of Two BSTs in OrderPHONE SCREEN · Seen Aug 2026
  • Rotate an Array In PlaceOA · PHONE SCREEN · Seen Aug 2026
All Adobe interview questionsSee Adobe hiring insights
Saved
public long sumEvenNodesOnPath(int a, int b) {
    // Write your code here.
}
Checking account…