Validate BST Interview Questions

Q: How do you validate a Binary Search Tree?

Problem: Verify every node in a binary tree satisfies BST ordering constraints. Optimal: Recurse with (node, min, max) bounds. Left child inherits max = node.val; right child inherits min = node.val. Reject if any node falls outside its range. Complexity: Time O(n), Space O(height) Alternative: Inorder traversal — values must be strictly increasing. Edge cases: Duplicates policy (usually left < node < right). Classic bug: only comparing node to parent, missing ancestor violations. Tip: BST validation is a standard tree medium and a common follow-up to 'what is a BST'.

Q: Why is 'left less than node less than right' not enough to validate a BST?

Because a node can satisfy the local parent check and still break an ancestor bound. Example: 5 on the left of 10, and 6 on the right of 5 — 6 is greater than 5 but it is still in 10's left subtree so it is illegal. I must pass a min and max range down, or do inorder and check strictly increasing. I would implement range DFS. I would not only compare each node to its parent. Tip: The local-check trap is why this question exists.

Q: Can you validate a BST with inorder traversal?

Yes. Inorder of a BST is sorted. I keep the previous value and fail if the current is not greater — or not greater-or-equal if they allow duplicates on one side, so I ask. I can do this recursively or with a stack. It is O(n) time and O(h) space. Range DFS is equivalent. I like inorder if the language makes 'previous' easy. I like ranges if they then ask me to print the invalid node. Tip: Inorder is the other accepted solution.

Q: Does a BST allow duplicate values? How does that change validation?

I ask. Some definitions put equals on the right, some forbid duplicates, some put them on the left. If equals are allowed on the right, the range check uses min less than or equal and max strictly greater, or the reverse. If I assume no duplicates and the tree has them, I will fail a valid tree. This is a 10-second clarifying question that looks senior. Tip: Duplicate policy is a classic BST gotcha.

Q: How would you recover a BST where two nodes were swapped?

Inorder should be sorted. Two swaps show up as two dips in the inorder sequence. I find those two nodes and swap their values. If they are adjacent in inorder, I see one dip. This is the 'recover BST' follow-up. I still use O(h) stack or Morris if they forbid extra space. I would not rebalance from scratch. They swapped two nodes. I swap them back. Tip: Recover BST is a common hard follow-up after validate.

Question 1

How do you validate a Binary Search Tree?

Answer

Problem

Verify every node in a binary tree satisfies BST ordering constraints.

Optimal

Recurse with (node, min, max) bounds. Left child inherits max = node.val; right child inherits min = node.val. Reject if any node falls outside its range. Complexity: Time O(n) , Space O(height)

Alternative: Inorder traversal — values must be strictly increasing.

Edge cases

Duplicates policy (usually left < node < right). Classic bug: only comparing node to parent, missing ancestor violations.

Question 2

Why is 'left less than node less than right' not enough to validate a BST?

Answer

Because a node can satisfy the local parent check and still break an ancestor bound. Example: 5 on the left of 10, and 6 on the right of 5 — 6 is greater than 5 but it is still in 10's left subtree so it is illegal. I must pass a min and max range down, or do inorder and check strictly increasing. I would implement range DFS. I would not only compare each node to its parent.

Question 3

Can you validate a BST with inorder traversal?

Answer

Yes. Inorder of a BST is sorted. I keep the previous value and fail if the current is not greater — or not greater-or-equal if they allow duplicates on one side, so I ask. I can do this recursively or with a stack. It is O(n) time and O(h) space. Range DFS is equivalent. I like inorder if the language makes 'previous' easy. I like ranges if they then ask me to print the invalid node.

Question 4

Does a BST allow duplicate values? How does that change validation?

Answer

I ask. Some definitions put equals on the right, some forbid duplicates, some put them on the left. If equals are allowed on the right, the range check uses min less than or equal and max strictly greater, or the reverse. If I assume no duplicates and the tree has them, I will fail a valid tree. This is a 10-second clarifying question that looks senior.

Question 5

How would you recover a BST where two nodes were swapped?

Answer

Inorder should be sorted. Two swaps show up as two dips in the inorder sequence. I find those two nodes and swap their values. If they are adjacent in inorder, I see one dip. This is the 'recover BST' follow-up. I still use O(h) stack or Morris if they forbid extra space. I would not rebalance from scratch. They swapped two nodes. I swap them back.

Validate BST Interview Questions

Questions (5)

Practice with AI mock interviews

Validate BST Interview Questions

Questions (5)

Related career resources

All DSA interview topics

Practice with AI mock interviews