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

Recall & Review

beginner

What does BST stand for and what is its key property?

BST stands for Binary Search Tree. Its key property is that for every node, all nodes in the left subtree have smaller values, and all nodes in the right subtree have larger values.

beginner

What is the main idea behind validating if a binary tree is a BST?

The main idea is to check if every node's value lies within a valid range defined by its ancestors, ensuring left children are smaller and right children are larger.

intermediate

In TypeScript, what type of traversal is commonly used to validate a BST?

In-order traversal is commonly used because it visits nodes in ascending order if the tree is a BST.

intermediate

Why can't we just check if left child < node < right child to validate BST?

Because this only checks immediate children, not the entire subtree. A node deeper in the left subtree might violate the BST property if it is greater than the root.

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 traversal order helps verify if a binary tree is a BST by checking ascending order?

A Post-order traversal

B Pre-order traversal

C Level-order traversal

D In-order traversal

In-order traversal visits nodes in ascending order if the tree is a BST.

What must be true for every node in a BST regarding its left subtree?

A All nodes in left subtree are smaller

B All nodes in left subtree are larger

C Left subtree can have any values

D Left subtree must be empty

In a BST, all nodes in the left subtree must have smaller values than the node.

Why is checking only immediate children insufficient to validate a BST?

A Because only root matters

B Because deeper nodes might violate BST property

C Because BST allows duplicates anywhere

D Because children can have equal values

Nodes deeper in the subtree might violate the BST property even if immediate children are correct.

What is the best way to keep track of valid value ranges when validating BST?

A Check only node values without range

B Use a queue to store nodes

C Pass min and max allowed values down the recursion

D Compare node with root only

Passing min and max allowed values ensures each node fits the BST property relative to ancestors.

What is the time complexity of validating a BST by visiting each node once?

A O(n)

B O(log n)

C O(n^2)

D O(1)

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

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

Think about how ancestors restrict node values.

Describe why in-order traversal output should be sorted for a BST and how this helps validation.

Consider the order nodes are visited in a BST.