Google·Software Engineer·Technical Phone Screen·Intermediate

IntermediatePrefer not to say

Apr 2026

Summary

Google coding interview with a number theory flavored tree problem. The kind of question that looks like a tree problem but is really just asking if you know how binary works.

Questions Asked (1)

Given a complete binary tree where nodes are indexed implicitly, find the index of a target node in O(log N) time by using the binary representation of indices to navigate left and right from the root.

Algorithms & Data StructuresTechnical Trade-offs

Author's notes

I went straight to thinking about tree traversal and almost wrote out a BFS before something clicked.

Create a free account to read the full note

AI HintsAI Generated

Suggested Approach

Explain that in a complete binary tree, the path from root to a node at index i can be derived from the binary representation of i (excluding the leading 1). Then, to find the index of a target node, perform a binary search on the index range [1, N], using the path derived from the mid index to navigate from the root and compare with the target. This yields O(log N) time because each path traversal takes O(log N) and binary search takes O(log N) steps.

Pro tip: Mention that this technique is used in real systems like binary heaps for efficient insertion and deletion, and that it avoids explicit pointers, saving memory. Also, clarify that the binary search assumes the tree is complete and the target exists; otherwise, handle edge cases.

1. Understand the implicit indexing

In a complete binary tree, nodes are numbered level by level from 1 to N. For any node i, its left child is 2i and right child is 2i+1. The path from root to i is given by the bits of i after the most significant bit: 0 means left, 1 means right.

2. Derive the navigation path

For a given index i, compute its binary representation, drop the leading 1, and interpret each remaining bit as a direction (0 for left, 1 for right) to traverse from the root.

3. Binary search on index range

Set low=1, high=N. While low <= high, compute mid = (low+high)/2, navigate to the node at index mid using the path from step 2, and compare its value with the target. Adjust low or high accordingly.

4. Analyze time complexity

Each navigation takes O(log N) time (height of tree), and binary search performs O(log N) iterations, resulting in O(log^2 N) time. However, if the tree is stored in an array, accessing the node at index mid is O(1), but the problem likely expects O(log N) for finding the index by value, which is not possible without additional structure. Clarify assumptions.

5. Discuss trade-offs and alternatives

If the tree is not stored in an array, the O(log^2 N) approach is standard. If the tree is stored in an array, we can simply scan the array in O(N) or use binary search if it's a BST. Emphasize that the implicit indexing is useful for heaps, not for searching by value.

Key Points to Mention

Complete binary tree properties: nodes filled level by level, left to right.
Implicit indexing: root at 1, children at 2i and 2i+1.
Binary representation of index gives path from root: drop leading 1, 0=left, 1=right.
Binary search on index range to find target value, assuming tree is a BST or values are ordered.
Time complexity: O(log N) for path traversal, O(log N) for binary search, total O(log^2 N) if not array-backed; O(log N) if array-backed and values are sorted.
Trade-offs: memory efficiency of implicit indexing vs. need for explicit pointers; applicability to heaps vs. search trees.

AI-generated suggestions, not part of the candidate's original notes. May be inaccurate — verify before relying on them.