Recall & Review
beginner
What does BST stand for and what is its main property?
BST stands for Binary Search Tree. Its main property is that for every node, all values in the left subtree are smaller, and all values in the right subtree are larger.
Click to reveal answer
beginner
What is the simplest way to check if a binary tree is a BST?
Perform an in-order traversal and check if the values are in strictly increasing order.
Click to reveal answer
intermediate
Why can't we just check the left and right child values to validate BST property?
Because the BST property applies to the entire subtree, not just immediate children. A node in the left subtree must be less than the current node, even if it's deeper down.
Click to reveal answer
intermediate
What role do minimum and maximum value limits play in BST validation?
They help ensure that all nodes in a subtree fall within valid value ranges, maintaining the BST property throughout the tree.
Click to reveal answer
beginner
Show the base case for a recursive BST validation function.
If the current node is null (empty), return true because an empty tree is a valid BST.
Click to reveal answer
Which traversal method helps check if a tree is a BST by producing sorted values?
✗ Incorrect
In-order traversal visits nodes in ascending order for BSTs, so checking if the output is sorted confirms the BST property.
What should be returned when the node is null during BST validation?
✗ Incorrect
An empty tree or subtree is considered a valid BST, so the function should return true.
If a node's value is not within the allowed min and max range during validation, what does it mean?
✗ Incorrect
Violating the min-max range means the BST property is broken, so the tree is not a BST.
Which of these is NOT a valid step in validating a BST?
✗ Incorrect
Checking if left child is greater than right child is not relevant; BST property depends on subtree values, not direct child comparison.
What is the time complexity of validating a BST using min-max recursion?
✗ Incorrect
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 min-max limits.
Think about how each subtree must fit within a range of allowed values.
You got /5 concepts.
Describe why an in-order traversal output can be used to check if a tree is a BST.
Consider the sorted order property of BST in in-order traversal.
You got /4 concepts.