House Robber III
Updated
Problem statement
The houses in a neighborhood form a binary tree. The only entrance is the root house, and every other house has exactly one parent house. Each house holds some money, given by its node value. If two houses that are directly linked (a parent and its child) are both robbed on the same night, the alarm goes off.
Given the root of the binary tree, return the maximum amount of money that can be robbed without robbing two directly linked houses.
Function
rob(root: TreeNode) → intExamples
Example 1
root = [3,2,3,null,3,null,1]return = 7- Rob the root (3) and the two grandchildren 3 and 1: 3 + 3 + 1 = 7.
- No two robbed houses are directly linked.
Example 2
root = [3,4,5,1,3,null,1]return = 9- Skip the root and rob its children 4 and 5: 4 + 5 = 9.
- Robbing the root instead gives at most 3 + 1 + 3 + 1 = 8.
Constraints
- The number of nodes in the tree is in the range
[1, 104]. 0 <= Node.val <= 104
More Okta interview questions
- Role-Based Network Access ControlPHONE SCREEN · Seen Aug 2026
- Lexicographically Smallest Dependency OrderPHONE SCREEN · Seen Aug 2026
- Simple Bank OperationsONSITE INTERVIEW · Seen Oct 2026
- Randomized Collection with Duplicate ValuesONSITE INTERVIEW · Seen Sep 2026
- Top-Down Employee Reporting ForestONSITE INTERVIEW · Seen Sep 2026
- Fair Multi-Tenant CacheONSITE INTERVIEW · Seen Aug 2026
- CD Rental SystemONSITE INTERVIEW · Seen Jun 2026
Similar questions at other companies
- House Robber IIIGoldman Sachs · PHONE SCREENGoldman Sachs interview questions
- House Robber IIIVisa · PHONE SCREENVisa interview questions
- Minimum Root-to-Leaf Cut CostGoogle · PHONE SCREEN · ONSITE INTERVIEWGoogle interview questions
- Maximum Nonadjacent Sum in a General TreeZip · PHONE SCREEN · ONSITE INTERVIEWZip interview questions
- Minimum-Cost Root-to-Leaf Path in an N-ary TreeBloomberg LP · PHONE SCREENBloomberg LP interview questions
- Lowest Common Manager for Employee GroupsAmazon · PHONE SCREEN
- File Encryption Tree OptimizationDatabricks · PHONE SCREEN · ONSITE INTERVIEWDatabricks interview questions
- Maximum Path Sum Between Marked NodesDoorDash · PHONE SCREENDoorDash interview questions
- Transitive Employee Referral CountsRobinhood · ONSITE INTERVIEWRobinhood interview questions
- Best Sum Downward Tree PathCitadel · OACitadel interview questions