Validate if Tree is BST in DSA Go - 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 left child < node < right child to validate BST?

Because the BST property applies to the entire left and right subtrees, not just immediate children. A violation can happen deeper in the subtree.

intermediate

What approach can we use to validate a BST efficiently?

Use recursion with a range of allowed values for each node. Initially, the range is infinite. For left child, update the upper bound; for right child, update the lower bound.

beginner

What is the time complexity of validating a BST using the range 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 Node value is equal to its children

B Left child < node and right child > node only

C All nodes in left subtree < node < all nodes in right subtree

D No condition is needed

The BST property requires all nodes in the left subtree to be less than the node, and all nodes in the right subtree to be greater.

What is the best way to validate a BST?

A Use recursion with min and max value limits

B Check immediate children only

C Traverse the tree randomly

D Count the number of nodes

Using recursion with min and max limits ensures all nodes satisfy BST properties throughout the tree.

What is the time complexity of validating a BST with n nodes?

A O(n)

B O(log n)

C O(1)

D O(n^2)

Each node is visited once, so the time complexity is O(n).

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

A Continue checking other nodes

B Return false immediately

C Ignore the violation

D Delete the node

The function should return false immediately when a violation is found.

Which traversal can help check if a tree is a BST by producing a sorted sequence?

A Preorder traversal

B Level order traversal

C Postorder traversal

D Inorder traversal

Inorder traversal of a BST produces nodes in ascending order.

Explain how to validate if a binary tree is a BST using recursion and value ranges.

Think about limiting the allowed values for each subtree.

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

Consider a node deep in the left subtree that violates the BST property.