Citadel·Software Engineer·Technical Phone Screen·Intermediate

IntermediatePrefer not to say

Jun 2026

Summary

Citadel software engineer interview with a classic BST implementation question. Nothing flashy, just raw coding under pressure and hoping you remember how in-order successor deletion actually works.

Questions Asked (1)

Implement a Binary Search Tree class in C++ from scratch, including insert, search, and delete operations. Your delete function must correctly handle leaf nodes, nodes with one child, and nodes with two children using in-order successor replacement.

Algorithms & Data StructuresTechnical Trade-offs

Author's notes

The insert and search parts were fine, knocked those out pretty quick.

Create a free account to read the full note

AI HintsAI Generated

Suggested Approach

Start by defining a TreeNode struct and a BST class with a root pointer. Implement insert and search iteratively for efficiency, then tackle delete recursively, handling the three cases (leaf, one child, two children) with in-order successor replacement. Test with edge cases like deleting the root and maintaining BST properties.

Pro tip: Mention that while recursion simplifies delete, it risks stack overflow for skewed trees; you can implement it iteratively or note the trade-off. Also, clarify that in-order successor is the leftmost node in the right subtree, and ensure you handle parent pointers if used.

1. Define the data structure

Create a TreeNode struct with key, left, right (and optionally parent) pointers, and a BST class with a root pointer. Include a constructor and destructor for memory management.

2. Implement insert and search

Write iterative insert and search functions that traverse the tree, comparing keys and updating pointers. Handle duplicates (e.g., ignore or update) based on requirements.

3. Implement delete with three cases

Write a recursive delete function that finds the node, then handles: (1) leaf: remove and return nullptr; (2) one child: replace with child; (3) two children: find in-order successor (leftmost in right subtree), copy its key, and recursively delete the successor.

4. Test and validate

Test with edge cases: empty tree, single node, deleting root, skewed trees, and random insert/delete sequences. Verify BST property after each operation.

Key Points to Mention

Time complexity: O(h) for insert, search, delete, where h is height; O(log n) for balanced, O(n) for skewed.
Space complexity: O(h) for recursive delete due to call stack; O(1) for iterative insert/search.
In-order successor is the leftmost node in the right subtree; alternatively, in-order predecessor can be used.
Handling of two-child case: copy successor's key and delete successor node, which has at most one child.
Memory management: avoid leaks by deleting nodes properly, especially in destructor.
Trade-offs: recursion vs iteration, parent pointers vs no parent pointers, and balancing (e.g., AVL/Red-Black) for performance.

AI-generated suggestions, not part of the candidate's original notes. May be inaccurate — verify before relying on them.