Maximum Sum of Non-Adjacent Nodes in a Binary Tree

Given a binary tree with integer values assigned to each node, select nodes such that their sum is maximum, ensuring no two adjacent nodes are picked.

Input:

The input consists of multiple test cases. The first line contains an integer 'T', the number of test cases.
For each test case, the binary tree is represented in level order in a single line with space-separated integers. Null nodes are represented by -1.
Example: 1 2 3 4 -1 5 6 -1 7 -1 -1 -1 -1 -1 -1

Output:

For each test case, output a single line with the maximum sum of non-adjacent nodes from the binary tree.

Example:

Consider the binary tree shown in the example image:

The maximum possible sum using non-adjacent nodes is 12.

Constraints:

  • 1 <= T <= 100
  • 0 <= N <= 3000 where N is the number of nodes in the binary tree.
  • 1 <= data <= 10^4 where data is the node value of the binary tree.
  • Time limit is 1 second per test case.

Note:

The tree nodes can only be summed according to adjacency rules, meaning if a node is chosen, its immediate children cannot be chosen.

AnswerBot
1d

Find the maximum sum of non-adjacent nodes in a binary tree.

  • Use dynamic programming to keep track of the maximum sum at each node considering whether to include or exclude the current node.

  • Recursively...read more

Help your peers!
Add answer anonymously...
Fidelity International Software Developer Intern Interview Questions
Stay ahead in your career. Get AmbitionBox app
qr-code
Helping over 1 Crore job seekers every month in choosing their right fit company
65 L+

Reviews

4 L+

Interviews

4 Cr+

Salaries

1 Cr+

Users/Month

Contribute to help millions

Made with ❤️ in India. Trademarks belong to their respective owners. All rights reserved © 2024 Info Edge (India) Ltd.

Follow us
  • Youtube
  • Instagram
  • LinkedIn
  • Facebook
  • Twitter