Last Node in Complete Binary Tree | Dataford Interview Questions

Given a complete binary tree (array/heap-style, parent = child/2 relation), find the last node in the tree in less than O(n) time.

The interviewer hinted at using the parent = child/2 index relationship to improve an O(n) solution. The candidate did not find the faster approach during the interview.

Implement find_last_node(heap). The input is a one-indexed array whose active nodes occupy a contiguous prefix, followed only by None values. Return the one-indexed position of the last active node, or 0 if the tree is empty.

Constraints

0 <= len(heap) <= 10^5
heap[0] is always None
Active nodes occupy positions 1 through n
All positions after n contain None

Function Signature

def find_last_node(heap):

Your question is Last Node in Complete Binary Tree. Start with the requirements in the Question tab.

Run and submit as often as you like. When you're ready, talk me through your approach or go straight to the code.

Problem

Given a complete binary tree (array/heap-style, parent = child/2 relation), find the last node in the tree in less than O(n) time.

The interviewer hinted at using the parent = child/2 index relationship to improve an O(n) solution. The candidate did not find the faster approach during the interview.

Constraints

0 <= len(heap) <= 10^5
heap[0] is always None
Active nodes occupy positions 1 through n
All positions after n contain None

Function Signature

def find_last_node(heap):

Your question is Last Node in Complete Binary Tree. Start with the requirements in the Question tab.

Run and submit as often as you like. When you're ready, talk me through your approach or go straight to the code.