Where it runs
1. The problem
You are building a small team from an org chart (a chart of who reports to whom). Each person has an "impact" score, and you want the highest total score. There is one rule: you can't put a manager and their direct report on the same team, because they would get in each other's way.
So you need a set of people with the highest total score that holds no pair "a boss and their direct report".
The easy guesses fail. Take everyone with a high score, and two of them turn out to be a manager and their report. Take every other level, and you may skip a strong person for no reason. You need a way that weighs, for each person, what they add against what taking them costs you lower in the tree.
This step is part of the paid track
The first 33 steps are open to everyone: lesson, exercise and tests. This one opens with full access. Start with a free account and the free steps.
Create a free accountSee what is includedmaxNonAdjacent(root) // root = [3, 4, 5, 1, 3, null, 1]Pick nodes with the biggest total so that no two picked nodes are parent and child. Each node will report two numbers: best with it taken, best with it skipped.
Recognise it
Say these words and it is this pattern
- best choice over a hierarchy or org chart
- cannot pick a node and its direct parent together
- post-order: children settled before the parent
- each node combines states from its children
Looks similar, isn't
- Tree traversal
That page is about the order of visiting. This one is about what gets carried back up.
- Dynamic programming (1-D)
A line has one direction, so an index is enough. Here the tree structure sets the order.
- Recursion with memoization
A tree has no repeated subproblems, so no cache is needed. Each node is visited once.
- Graph BFS / DFS
A general graph can reach a node twice, so the recursion may not end. A tree cannot.
n nodes give O(n) when each node does O(1) work. Several states per node multiply that.
On LeetCode
Tree problems where each node returns two or three numbers to its parent, such as the best total with this node taken and without it. One post-order walk computes them from the leaves up.
The lesson task on a binary tree. Return the taken and the skipped total for each node.
Each subtree returns its coins minus its nodes, and the moves across its top edge are the absolute value of that number.
Each node returns the best path going down from it, and the answer at that node joins its two best downward paths.
Each node returns one of three states, has a camera, is covered or needs a camera, and the parent decides from its children's states.