Binary Tree Property Maintenance | Dataford Interview Questions

Given a perfect binary tree with node values 0 or 1 and the property that a node is 1 only if both children are 1, implement clear() and set() APIs that operate starting from the leaf level and fix up the remaining nodes to maintain the property.

The task was asked in the Coding-2 stage. Represent the tree as a zero-based level-order array, and identify leaves by their zero-based position from left to right.

Input and Output

Implement update_tree(tree, operations). tree is a valid perfect binary tree array. Each operation is ["set" or "clear", leaf_index]. Set or clear the selected leaf, recompute every ancestor on its path, and return the updated array. An internal node equals 1 exactly when both children equal 1.

Constraints

The tree length is 2^h - 1 for an integer h >= 1.
1 <= tree.length <= 131071
Each tree value is either 0 or 1.
0 <= leaf_index < 2^(h - 1).
1 <= len(operations) <= 10000.
Every input tree satisfies the stated invariant.

Function Signature

def update_tree(tree, operations):

Your question is Binary Tree Property Maintenance. 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