Problem 1: Balanced Binary Search Tree (BST) Validation
Concept: Data Structures (Binary Search Trees), Recursion
Problem Description:
A binary search tree (BST) is a binary tree where for each node:
• All nodes in the left subtree have values less than the node's value.
• All nodes in the right subtree have values greater than the node's value.
A balanced BST is one where the heights of the left and right subtrees of any node differ by at
most 1. (AVL or Red-Black tree properties are not required; just the height difference
condition.)
The following code is intended to check if a given binary tree is both a valid BST and balanced.
The isValidBST function should return true if the tree meets both criteria, and false otherwise.
The isBalanced function should check the tree balance. The isValidBSTHelper checks if the
tree is a valid BST. Find and fix the bugs.
Language: Java
Code:
class Node {
int data;
Node left, right;
public Node(int data) {
this.data = data;
left = right = null;
}
}
public class BSTValidator {
public static boolean isValidBST(Node root) {
return isValidBSTHelper(root, null, null) && isBalanced(root);
}
private static boolean isValidBSTHelper(Node node, Integer min, Integer max) {
if (node == null) {
return true;
}
if ((min != null && node.data <= min) || (max != null && node.data >= max)) { //Bug: strict
inequality needed
return false;
}
return isValidBSTHelper(node.left, min, node.data) && isValidBSTHelper(node.right,
node.data, max);
}
public static boolean isBalanced(Node root) {
if (root == null) {
return true;
}
int leftHeight = getHeight(root.left);
int rightHeight = getHeight(root.right);
if (Math.abs(leftHeight - rightHeight) > 1) {
return false;
}
return isBalanced(root.left) && isBalanced(root.right);
}
private static int getHeight(Node node) {
if (node == null) {
return 1; //Bug: should return 0
}
return 1 + Math.max(getHeight(node.left), getHeight(node.right));
}
public static void main(String[] args) {
Node root1 = new Node(5);
root1.left = new Node(3);
root1.right = new Node(7);
root1.left.left = new Node(2);
root1.left.right = new Node(4);
System.out.println("Is valid BST and balanced? " + isValidBST(root1)); // Expected: true
Node root2 = new Node(5);
root2.left = new Node(3);
root2.right = new Node(7);
root2.left.left = new Node(1);
root2.left.right = new Node(4);
root2.right.right = new Node(8);
root2.right.right.right = new Node(9); //Unbalanced
System.out.println("Is valid BST and balanced? " + isValidBST(root2)); // Expected: false
Node root3 = new Node(5);
root3.left = new Node(3);
root3.right = new Node(7);
root3.left.left = new Node(1);
root3.left.right = new Node(6); //Not a valid BST
System.out.println("Is valid BST and balanced? " + isValidBST(root3)); // Expected: false
}
}
Test Cases:
1. Valid and balanced BST (as in root1): Expected true
2. Valid but unbalanced BST (as in root2): Expected false
3. Invalid BST (as in root3): Expected false
4. Empty tree (null root): Expected true
5. Single node tree: Expected true
6. A valid BST where a node's value equals min or max: Expected false
Bugs:
1. BST Validation - Incorrect Inequality: The isValidBSTHelper function uses non-strict
inequalities (<= and >=) when checking if a node's value is within the allowed range. This
violates the BST property, where left subtree nodes must be strictly less than the current node,
and right subtree nodes must be strictly greater than .
2. getHeight Base Case: The getHeight function returns 1 when the node is null. The correct
base case should return 0 because a null node has a height of 0.
Solution:
class Node {
int data;
Node left, right;
public Node(int data) {
this.data = data;
left = right = null;
}
}
public class BSTValidator {
public static boolean isValidBST(Node root) {
return isValidBSTHelper(root, null, null) && isBalanced(root);
}
private static boolean isValidBSTHelper(Node node, Integer min, Integer max) {
if (node == null) {
return true;
}
if ((min != null && node.data >= min) || (max != null && node.data <= max)) {
return false;
}
return isValidBSTHelper(node.left, min, node.data) && isValidBSTHelper(node.right,
node.data, max);
}
public static boolean isBalanced(Node root) {
if (root == null) {
return true;
}
int leftHeight = getHeight(root.left);
int rightHeight = getHeight(root.right);
if (Math.abs(leftHeight - rightHeight) > 1) {
return false;
}
return isBalanced(root.left) && isBalanced(root.right);
}
private static int getHeight(Node node) {
if (node == null) {
return 0;
}
return 1 + Math.max(getHeight(node.left), getHeight(node.right));
}
public static void main(String[] args) {
Node root1 = new Node(5);
root1.left = new Node(3);
root1.right = new Node(7);
root1.left.left = new Node(2);
root1.left.right = new Node(4);
System.out.println("Is valid BST and balanced? " + isValidBST(root1)); // Expected: true
Node root2 = new Node(5);
root2.left = new Node(3);
root2.right = new Node(7);
root2.left.left = new Node(1);
root2.left.right = new Node(4);
root2.right.right = new Node(8);
root2.right.right.right = new Node(9); //Unbalanced
System.out.println("Is valid BST and balanced? " + isValidBST(root2)); // Expected: false
Node root3 = new Node(5);
root3.left = new Node(3);
root3.right = new Node(7);
root3.left.left = new Node(1);
root3.left.right = new Node(6); //Not a valid BST
System.out.println("Is valid BST and balanced? " + isValidBST(root3)); // Expected: false
}
}
Problem 1: Balanced Binary Search Tree (BST) Validation
C Version
Code: #include <stdio.h>
#include <stdlib.h>
#include <stdbool.h>
#include <limits.h> // For INT_MAX and INT_MIN
typedef struct Node {
int data;
struct Node *left, *right;
} Node;
Node* createNode(int data) {
Node* newNode = (Node*)malloc(sizeof(Node));
newNode->data = data;
newNode->left = newNode->right = NULL;
return newNode;
}
bool isValidBSTHelper(Node* node, int min, int max) {
if (node == NULL) {
return true;
}
if (node->data <= min || node->data >= max) { // Bug: <= and >= should be < and >
return false;
}
return isValidBSTHelper(node->left, min, node->data) && isValidBSTHelper(node->right,
node->data, max);
}
bool isValidBST(Node* root) {
return isValidBSTHelper(root, INT_MIN, INT_MAX);
}
int getHeight(Node* node) {
if (node == NULL) {
return 1; // Bug: Should return 0
}
int leftHeight = getHeight(node->left);
int rightHeight = getHeight(node->right);
return 1 + (leftHeight > rightHeight ? leftHeight : rightHeight);
}
bool isBalanced(Node* root) {
if (root == NULL) {
return true;
}
int leftHeight = getHeight(root->left);
int rightHeight = getHeight(root->right);
if (abs(leftHeight - rightHeight) > 1) {
return false;
}
return isBalanced(root->left) && isBalanced(root->right);
}
bool isValidBSTAndBalanced(Node* root) {
return isValidBST(root) && isBalanced(root);
}
int main() {
Node* root1 = createNode(5);
root1->left = createNode(3);
root1->right = createNode(7);
root1->left->left = createNode(2);
root1->left->right = createNode(4);
printf("Is valid BST and balanced? %s\n", isValidBSTAndBalanced(root1) ? "true" : "false"); //
Expected: true
Node* root2 = createNode(5);
root2->left = createNode(3);
root2->right = createNode(7);
root2->left->left = createNode(1);
root2->left->right = createNode(4);
root2->right->right = createNode(8);
root2->right->right->right = createNode(9);
printf("Is valid BST and balanced? %s\n", isValidBSTAndBalanced(root2) ? "true" : "false"); //
Expected: false
Node* root3 = createNode(5);
root3->left = createNode(3);
root3->right = createNode(7);
root3->left->left = createNode(1);
root3->left->right = createNode(6);
printf("Is valid BST and balanced? %s\n", isValidBSTAndBalanced(root3) ? "true" : "false"); //
Expected: false
return 0;
}
Bugs: Same as the Java version: strict inequality and incorrect base case for getHeight.
C++ Version
Code: #include <iostream>
#include <algorithm>
#include <limits> // for numeric_limits
using namespace std;
struct Node {
int data;
Node *left, *right;
Node(int data) : data(data), left(nullptr), right(nullptr) {}
};
bool isValidBSTHelper(Node* node, int min, int max) {
if (!node) {
return true;
}
if (node->data <= min || node->data >= max) { // Bug: <= and >= should be < and >
return false;
}
return isValidBSTHelper(node->left, min, node->data) && isValidBSTHelper(node->right,
node->data, max);
}
bool isValidBST(Node* root) {
return isValidBSTHelper(root, numeric_limits<int>::min(), numeric_limits<int>::max());
}
int getHeight(Node* node) {
if (!node) {
return 1; // Bug: should return 0
}
return 1 + max(getHeight(node->left), getHeight(node->right));
}
bool isBalanced(Node* root) {
if (!root) {
return true;
}
int leftHeight = getHeight(root->left);
int rightHeight = getHeight(root->right);
if (abs(leftHeight - rightHeight) > 1) {
return false;
}
return isBalanced(root->left) && isBalanced(root->right);
}
bool isValidBSTAndBalanced(Node* root) {
return isValidBST(root) && isBalanced(root);
}
int main() {
Node* root1 = new Node(5);
root1->left = new Node(3);
root1->right = new Node(7);
root1->left->left = new Node(2);
root1->left->right = new Node(4);
cout << "Is valid BST and balanced? " << (isValidBSTAndBalanced(root1) ? "true" : "false")
<< endl; // Expected: true
Node* root2 = new Node(5);
root2->left = new Node(3);
root2->right = new Node(7);
root2->left->left = new Node(1);
root2->left->right = new Node(4);
root2->right->right = new Node(8);
root2->right->right->right = new Node(9);
cout << "Is valid BST and balanced? " << (isValidBSTAndBalanced(root2) ? "true" : "false")
<< endl; // Expected: false
Node* root3 = new Node(5);
root3->left = new Node(3);
root3->right = new Node(7);
root3->left->left = new Node(1);
root3->left->right = new Node(6);
cout << "Is valid BST and balanced? " << (isValidBSTAndBalanced(root3) ? "true" : "false")
<< endl; // Expected: false
return 0;
}
Bugs: Same bugs as the Java version.
Problem 2: Concurrent Bank Account Operations
Concept: Concurrency, Threads, Synchronization
Problem Description:
The following Java code simulates a bank account with multiple threads performing deposit and
withdrawal operations. The BankAccount class manages the account balance. The Transaction
class represents a deposit or withdrawal. The goal is to ensure that the account balance
remains consistent even with concurrent transactions. However, the current implementation has
race conditions that can lead to incorrect balances. Find and fix the bugs.
Language: Java
Code:
public class BankAccount {
private double balance;
public BankAccount(double initialBalance) {
this.balance = initialBalance;
}
public double getBalance() {
return balance;
}
public void deposit(double amount) {
balance += amount; //Race condition
}
public void withdraw(double amount) {
balance -= amount; //Race condition
}
}
class Transaction implements Runnable {
private BankAccount account;
private double amount;
private boolean isDeposit;
public Transaction(BankAccount account, double amount, boolean isDeposit) {
this.account = account;
this.amount = amount;
this.isDeposit = isDeposit;
}
@Override
public void run() {
if (isDeposit) {
account.deposit(amount);
} else {
account.withdraw(amount);
}
}
}
public class ConcurrentTransactions {
public static void main(String[] args) throws InterruptedException {
BankAccount account = new BankAccount(1000);
// Create multiple deposit and withdrawal transactions
Transaction deposit1 = new Transaction(account, 200, true);
Transaction withdraw1 = new Transaction(account, 100, false);
Transaction deposit2 = new Transaction(account, 300, true);
Transaction withdraw2 = new Transaction(account, 150, false);
// Create and start threads
Thread thread1 = new Thread(deposit1);
Thread thread2 = new Thread(withdraw1);
Thread thread3 = new Thread(deposit2);
Thread thread4 = new Thread(withdraw2);
thread1.start();
thread2.start();
thread3.start();
thread4.start();
// Wait for threads to finish
thread1.join();
thread2.join();
thread3.join();
thread4.join();
// Print the final balance
System.out.println("Final balance: " + account.getBalance()); //Expected: 1250, but often
incorrect due to race conditions
}
}
Test Cases:
1. Initial balance = 1000, Deposits = 200 + 300, Withdrawals = 100 + 150. Expected final
balance: 1250. Run the program multiple times; the balance should always be 1250. If it's not,
there's a race condition.
2. Increase the number of threads and transactions to make the race condition more apparent.
3. Try different deposit and withdrawal amounts.
Bugs:
1. Race Condition: The deposit and withdraw methods in the BankAccount class are not
thread-safe. Multiple threads can access and modify the balance variable concurrently, leading
to race conditions. This can result in lost updates, where some transactions are not reflected in
the final balance.
Solution:
public class BankAccount {
private double balance;
public BankAccount(double initialBalance) {
this.balance = initialBalance;
}
public double getBalance() {
return balance;
}
public synchronized void deposit(double amount) {
balance += amount; //Race condition
}
public synchronized void withdraw(double amount) {
balance -= amount; //Race condition
}
}
class Transaction implements Runnable {
private BankAccount account;
private double amount;
private boolean isDeposit;
public Transaction(BankAccount account, double amount, boolean isDeposit) {
this.account = account;
this.amount = amount;
this.isDeposit = isDeposit;
}
@Override
public void run() {
if (isDeposit) {
account.deposit(amount);
} else {
account.withdraw(amount);
}
}
}
public class ConcurrentTransactions {
public static void main(String[] args) throws InterruptedException {
BankAccount account = new BankAccount(1000);
// Create multiple deposit and withdrawal transactions
Transaction deposit1 = new Transaction(account, 200, true);
Transaction withdraw1 = new Transaction(account, 100, false);
Transaction deposit2 = new Transaction(account, 300, true);
Transaction withdraw2 = new Transaction(account, 150, false);
// Create and start threads
Thread thread1 = new Thread(deposit1);
Thread thread2 = new Thread(withdraw1);
Thread thread3 = new Thread(deposit2);
Thread thread4 = new Thread(withdraw2);
thread1.start();
thread2.start();
thread3.start();
thread4.start();
// Wait for threads to finish
thread1.join();
thread2.join();
thread3.join();
thread4.join();
// Print the final balance
System.out.println("Final balance: " + account.getBalance()); //Expected: 1250, but often
incorrect due to race conditions
}
}
Important Notes on the Concurrency Problem
• Unpredictability: Race conditions are notoriously difficult to debug because they are non-
deterministic. The bug may not manifest every time the program is run.
• Explanation: Contestants should understand why the race condition occurs (the interleaved
execution of the += and -= operations) and how synchronized solves it (by ensuring that only
one thread can execute the deposit or withdraw method at a time).
• Alternative Solutions: While synchronized is the simplest solution here, you could also
discuss other concurrency control mechanisms, such as locks or atomic variables.
These two problems provide a good mix of data structure/algorithm debugging and concurrency
debugging, both relevant to college-level computer science. Remember to provide clear
problem descriptions, test cases, and sufficient time for contestants to analyze and fix the code.
C Version
Note: Concurrency in C is more complex because it requires using pthreads and explicit
locking mechanisms. This version is designed to be challenging.
Code: #include <stdio.h>
#include <stdlib.h>
#include <pthread.h>
typedef struct {
double balance;
pthread_mutex_t mutex;
} BankAccount;
typedef struct {
BankAccount* account;
double amount;
int isDeposit; // 1 for deposit, 0 for withdrawal
} TransactionArgs;
void initBankAccount(BankAccount* account, double initialBalance) {
account->balance = initialBalance;
pthread_mutex_init(&account->mutex, NULL);
}
double getBalance(BankAccount* account) {
return account->balance; // Bug: Missing mutex lock
}
void deposit(BankAccount* account, double amount) {
pthread_mutex_lock(&account->mutex);
account->balance += amount;
pthread_mutex_unlock(&account->mutex);
}
void withdraw(BankAccount* account, double amount) {
pthread_mutex_lock(&account->mutex);
account->balance -= amount;
pthread_mutex_unlock(&account->mutex);
}
void* transaction(void* arg) {
TransactionArgs* args = (TransactionArgs*)arg;
if (args->isDeposit) {
deposit(args->account, args->amount);
} else {
withdraw(args->account, args->amount);
}
return NULL;
}
int main() {
BankAccount account;
initBankAccount(&account, 1000.0);
pthread_t threads[4];
TransactionArgs args[4];
//Transactions
args[0] = (TransactionArgs){&account, 200.0, 1};
args[1] = (TransactionArgs){&account, 100.0, 0};
args[2] = (TransactionArgs){&account, 300.0, 1};
args[3] = (TransactionArgs){&account, 150.0, 0};
//Create Threads
for (int i = 0; i < 4; i++) {
pthread_create(&threads[i], NULL, transaction, &args[i]);
}
//Join Threads
for (int i = 0; i < 4; i++) {
pthread_join(threads[i], NULL);
}
pthread_mutex_lock(&account.mutex);
printf("Final balance: %.2f\n", account.balance); // Expected: 1250.00
pthread_mutex_unlock(&account.mutex);
pthread_mutex_destroy(&account.mutex);
return 0;
}
Bugs:
1. Missing Mutex Lock in getBalance: The getBalance function directly accesses the balance
without acquiring the mutex. This can lead to a race condition where getBalance reads an
inconsistent value while another thread is modifying the balance. While this doesn't directly
cause incorrect updates , it violates the principle of thread safety and can lead to unexpected
behavior in more complex scenarios.
2. No Mutex Lock: Mutex lock in main before printing the final balance.
C++ Version
Code: #include <iostream>
#include <thread>
#include <mutex>
using namespace std;
class BankAccount {
private:
double balance;
mutex mtx;
public:
BankAccount(double initialBalance) : balance(initialBalance) {}
double getBalance() const {
std::lock_guard<std::mutex> lock(mtx);
return balance; // Corrected: Now thread-safe
}
void deposit(double amount) {
std::lock_guard<std::mutex> lock(mtx);
balance += amount;
}
void withdraw(double amount) {
std::lock_guard<std::mutex> lock(mtx);
balance -= amount;
}
};
void transaction(BankAccount& account, double amount, bool isDeposit) {
if (isDeposit) {
account.deposit(amount);
} else {
account.withdraw(amount);
}
}
int main() {
BankAccount account(1000.0);
thread threads[4];
// Transactions
threads[0] = thread(transaction, ref(account), 200.0, true);
threads[1] = thread(transaction, ref(account), 100.0, false);
threads[2] = thread(transaction, ref(account), 300.0, true);
threads[3] = thread(transaction, ref(account), 150.0, false);
// Join Threads
for (int i = 0; i < 4; i++) {
threads[i].join();
}
cout << "Final balance: " << account.getBalance() << endl; // Expected: 1250.00
return 0;
}
Bugs:
1. The getBalance() method is missing a std::lock_guard. As a result, getBalance() might read
inconsistent values and lead to undefined behaviors.
These C and C++ versions are designed to be more challenging, especially the concurrency
problem in C, due to the need for explicit thread management and synchronization. Remember
to emphasize the importance of thread safety and proper locking mechanisms when presenting
these problems.
