Validate if Tree is BST in DSA C++ - Cheat Sheet & Quick Revision

Recall & Review

beginner

What is a Binary Search Tree (BST)?

A Binary Search Tree is a tree where each node has at most two children. For every node, all nodes in its left subtree have smaller values, and all nodes in its right subtree have larger values.

beginner

What is the main property to check when validating if a tree is a BST?

We must ensure that for every node, all values in the left subtree are less than the node's value, and all values in the right subtree are greater than the node's value.

intermediate

Why can't we just check if the left child is less and right child is greater to validate a BST?

Because the BST property applies to all descendants, not just immediate children. A node deep in the left subtree must be less than the root, not just its parent.

intermediate

What is a common approach to validate a BST using recursion?

Use a helper function that passes down the allowed minimum and maximum values for each node. Check if the node's value lies within these limits, then recursively check left and right subtrees with updated limits.

beginner

What is the time complexity of validating a BST using the min/max recursion method?

The time complexity is O(n), where n is the number of nodes, because each node is visited once.

Which condition must hold true for every node in a BST?

A Left subtree nodes < node < Right subtree nodes

B Left subtree nodes > node > Right subtree nodes

C Left child < node and Right child > node only

D All nodes have two children

In a BST, all nodes in the left subtree must be less than the node, and all nodes in the right subtree must be greater.

What is the best way to validate a BST?

A Check only immediate children values

B Use inorder traversal and check if sorted

C Check if root is greater than left child

D Count nodes in the tree

Inorder traversal of a BST produces sorted values. Checking if the inorder traversal is sorted validates the BST.

What does the min/max recursion method do when validating a BST?

A Swaps nodes to fix the tree

B Counts nodes in left and right subtree

C Checks only leaf nodes

D Passes allowed value range down the tree

The method passes minimum and maximum allowed values to each node to ensure BST property holds.

What is the time complexity of validating a BST using inorder traversal?

A O(n)

B O(log n)

C O(n log n)

D O(n^2)

Inorder traversal visits each node once, so the time complexity is O(n).

If a node violates the BST property, what should the validation function return?

A True

B Null

C False

D The node value

If any node violates the BST property, the tree is not a BST, so the function returns False.

Explain how to validate if a binary tree is a BST using recursion with min and max limits.

Think about how allowed value ranges change as you go down the tree.

Describe why checking only immediate children is not enough to validate a BST.

Consider a node far down the left subtree with a value greater than root.