How do I practice coding and algorithm questions?

Use PracHub's coding console to write, test, and debug your solutions in Python or JavaScript. View hints, test against sample inputs, and compare with official solutions.

What difficulty level is this coding question?

This is a hard difficulty Coding & Algorithms question, commonly asked during Onsite rounds at Airbnb.

What role is this question designed for?

This question is commonly asked for Software Engineer candidates at Airbnb during technical interviews.

Maximize sum with no adjacent tree nodes

Quick Overview

This question evaluates understanding of tree-based dynamic programming and stateful optimization for selecting non-adjacent nodes, testing algorithmic problem-solving and data structure knowledge in the Coding & Algorithms domain while requiring both conceptual understanding of recurrence/state relationships and practical implementation skills.

Company: Airbnb

Role: Software Engineer

Category: Coding & Algorithms

Difficulty: hard

Interview Round: Onsite

Given the root of a binary tree where each node contains an integer value (can be 0 or positive), choose a subset of nodes such that **no selected node is directly connected to another selected node** (i.e., you cannot select both a parent and its child). ### Task Return the **maximum possible sum** of the selected node values. ### Input - `root`: root node of a binary tree. ### Output - An integer: the maximum sum under the constraint. ### Constraints (typical) - Up to `1e5` nodes. - Tree is not necessarily balanced.

Quick Answer: This question evaluates understanding of tree-based dynamic programming and stateful optimization for selecting non-adjacent nodes, testing algorithmic problem-solving and data structure knowledge in the Coding & Algorithms domain while requiring both conceptual understanding of recurrence/state relationships and practical implementation skills.

You are given the root of a binary tree. Each node contains a non-negative integer value. Select a subset of nodes such that no selected node is directly connected to another selected node, meaning you cannot select both a parent and its child. Siblings may both be selected. Return the maximum possible sum of the selected node values. For this problem, the tree is provided as a level-order list representation using `None` for missing children.

Constraints

0 <= number of non-null nodes <= 100000
0 <= node values <= 10^9
The tree is not necessarily balanced
The input list uses level-order traversal with `None` placeholders for missing children

Examples

Input: [3, 2, 3, None, 3, None, 1]

Expected Output: 7

Explanation: Select the root (3), the left-right grandchild (3), and the right-right grandchild (1). Total = 7.

Input: [3, 4, 5, 1, 3, None, 1]

Expected Output: 9

Explanation: The best choice is to skip the root and take nodes 4 and 5. Total = 9.

Input: []

Expected Output: 0

Explanation: An empty tree has no nodes to select.

Input: [10]

Expected Output: 10

Explanation: With only one node, the maximum sum is its value.

Input: [0, 0, 0, 5, None, None, 5]

Expected Output: 10

Explanation: The best choice is to take the two leaf nodes with value 5. Total = 10.

Hints

For each node, think about two states: the best sum if you take this node, and the best sum if you skip it.
A postorder traversal is useful because you need the answers for both children before computing the answer for the parent.

Quick Overview