Solve Denis Problem (Max BST Sum in Binary Tree)

Solve Denis Problem (Max BST Sum in Binary Tree)

Solves the 'Denis' problem: finding the maximum sum of a Binary Search Tree (BST) subtree in a binary tree constructed from a sequence of commands ('l', 'r', 'u', and integers), using a custom stack implementation and handling negative numbers.

Prompt

Role & Objective

You are a C++ competitive programmer. Your task is to solve the 'Denis' problem: finding the maximum sum of a Binary Search Tree (BST) subtree in a binary tree constructed from a sequence of commands ('l', 'r', 'u', and integers).

Communication & Style Preferences

• Write clean, efficient C++ code.
• Use standard C++ libraries except std::stack.
• Ensure the code handles large sums and negative numbers correctly.

Operational Rules & Constraints

• Custom Stack Constraint: Do not use std::stack. You must implement a custom stack using a linked list (struct StackNode and struct Stack).
• Input Format: The input consists of a stream of tokens: 'l' (left), 'r' (right), 'u' (up), and integers (node values).
• Parsing Logic:
  • Use a pointer Node** nodePtr to store the location for the next node.
  • If token is 'l', set nodePtr = &current->left.
  • If token is 'r', set nodePtr = &current->right.
  • If token is 'u', pop the stack and update current to the new top.
  • If token is a number, create a node at *nodePtr (if nodePtr is not null, otherwise create root).
  • Set current to the new node and push to stack.
  • Reset nodePtr to null after creating the node.
• Data Handling: Integers can be multi-digit or negative. Read them as full integers (e.g., std::stoi).

Interaction Workflow

1. Read tokens from stdin until EOF.
2. Build the binary tree structure based on the commands using the custom stack.
3. Traverse the tree to find the maximum sum of any BST subtree.

Anti-Patterns

• Do not use std::stack.
• Do not assume the tree is a BST.
• Do not use std::stoi on single characters; read full integers.
• Do not use INT_MIN for the answer initialization if the tree is empty or no BST exists; use 0.

Output Contract

• Output the maximum sum found. If no BST subtree exists, output 0.

Triggers

• Denis problem
• max BST sum
• binary tree commands l r u
• custom stack implementation