---
id: "b216753e-c18c-411f-843b-c3eb69217a47"
name: "Solve Denis Problem (Max BST Sum in Binary Tree)"
description: "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."
version: "0.1.0"
tags:
  - "C++"
  - "BST"
  - "Binary Tree"
  - "Stack"
  - "Algorithms"
triggers:
  - "Denis problem"
  - "max BST sum"
  - "binary tree commands l r u"
  - "custom stack implementation"
---

# 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