---
title: "BST properties and recursive search"
subject: "Data Structure and Algorithm"
chapter: 6
key: "semester_4/data_structure_and_algorithm:bst-properties-recursive-search"
source: https://www.bctengineer.com/q/semester_4/data_structure_and_algorithm/bst-properties-recursive-search
site: BCT Engineering
---

# BST properties and recursive search

Data Structure and Algorithm · Chapter 6: Trees

- Asked in: 2069 Poush, 3+5 marks
- Video: [Lec-53: Binary Search Tree in Data Structure | Insertion and Traversal in BST](https://www.youtube.com/watch?v=sXABdGalFNg) — Gate Smashers
- Answer checked by Claude Opus 5.5 (high effort) on 2026-10-14
- Page: https://www.bctengineer.com/q/semester_4/data_structure_and_algorithm/bst-properties-recursive-search
- Whole chapter: https://www.bctengineer.com/md/semester_4/data_structure_and_algorithm/chapter-6

## Question

What are the properties of a Binary Search Tree (BST)? Explain recursive algorithm to search a BST.

## Short answer

BST properties: left subtree keys < node < right subtree keys; in-order yields sorted order. Recursive search: compare key with root; if equal return node; if less recurse left; else right; null if not found. O(h) time.

## Answer

#### Properties of a Binary Search Tree
1. It is a binary tree: every node has at most two children (left and right).
2. All keys in the left subtree of a node are smaller than the node's key.
3. All keys in the right subtree of a node are greater than the node's key (duplicates are usually not allowed, or are always placed on one side).
4. The left and right subtrees are themselves binary search trees.
5. In-order traversal visits the keys in ascending order.
6. Search, insertion and deletion take O(h) time; h = log n for a balanced tree and n for a skewed one.

#### Recursive search algorithm
Compare the key with the root. If equal, found; if smaller, search the left subtree; otherwise search the right subtree.

```text
Search(node, key)
1. if node = NULL        return NULL          (not found)
2. if key = node->info   return node          (found)
3. if key < node->info   return Search(node->left, key)
4. else                  return Search(node->right, key)
```
```c
struct node *search(struct node *root, int key) {
    if (root == NULL || root->info == key)
        return root;                       /* empty tree or found */
    if (key < root->info)
        return search(root->left, key);    /* go left */
    return search(root->right, key);       /* go right */
}
```
Example: BST with root 50 (left 30, right 70; 30 has children 20, 40). Searching 40: 40 < 50 go left; 40 > 30 go right; 40 = 40 found. Three comparisons, one for each node on the path.

Time complexity is O(h): best O(1), average O(log n), worst O(n) for a skewed tree. The recursion depth is also at most h.

## Check yourself

The answer's key points as multiple-choice questions, with the correct option and why.

1. What is the key property of a BST?
   A. Left subtree keys are smaller and right subtree keys are greater than the node's key
   B. Left subtree keys are larger
   C. Both subtrees have equal size
   D. All keys are equal
   Answer: A. Applied at every node, this makes search efficient. (Key point: Ordering property)

2. What does inorder traversal of a BST give?
   A. Keys in descending order
   B. Keys in insertion order
   C. Keys in ascending order
   D. Keys level by level
   Answer: C. Left, node, right visits smaller keys first. (Key point: Inorder)

3. In recursive search, if key < node->info, what is done?
   A. Search the left subtree
   B. Search the right subtree
   C. Return the node
   D. Return NULL
   Answer: A. Smaller keys lie in the left subtree. (Key point: Recursive search)

4. What is the worst-case search time and when does it occur?
   A. O(1) for a skewed tree
   B. O(log n) for a skewed tree
   C. O(n) for a skewed tree
   D. O(n^2)
   Answer: C. Search costs O(h), and a skewed tree has h = n. (Key point: Complexity)

## Related in Data Structure and Algorithm

- [Binary tree traversals; preorder of BST](https://www.bctengineer.com/question.md?key=semester_4%2Fdata_structure_and_algorithm%3Abinary-tree-traversal-methods-preorder) — Data Structure and Algorithm, chapter 6
- [Binary search with algorithm and example](https://www.bctengineer.com/question.md?key=semester_4%2Fdata_structure_and_algorithm%3Abinary-search-algorithm-example) — Data Structure and Algorithm, chapter 8, asked 4×
- [Binary search for 54 in sorted data](https://www.bctengineer.com/question.md?key=semester_4%2Fdata_structure_and_algorithm%3Abinary-search-54) — Data Structure and Algorithm, chapter 8
- [Binary search for 89; hash functions](https://www.bctengineer.com/question.md?key=semester_4%2Fdata_structure_and_algorithm%3Abinary-search-89-hashing) — Data Structure and Algorithm, chapter 8
- [Complexity of binary search](https://www.bctengineer.com/question.md?key=semester_4%2Fdata_structure_and_algorithm%3Abinary-search-complexity) — Data Structure and Algorithm, chapter 8
- [Sequential vs binary search](https://www.bctengineer.com/question.md?key=semester_4%2Fdata_structure_and_algorithm%3Asequential-vs-binary-search) — Data Structure and Algorithm, chapter 8

## Related in other subjects

- [Recursive language and its properties](https://www.bctengineer.com/question.md?key=semester_3%2Ftheory_of_computation%3Arecursive-language-properties) — Theory of Computation, chapter 4, asked 2×
- [Decision tree classifier and Hunt's algorithm](https://www.bctengineer.com/question.md?key=semester_7%2Fdata_mining%3Adecision-tree-hunt) — Data Mining, chapter 3
- [Define tree; properties and applications](https://www.bctengineer.com/question.md?key=semester_4%2Fdiscrete_structure%3Atree-definition-properties-applications) — Discrete Structure, chapter 4
- [Random number properties; KS test algorithm](https://www.bctengineer.com/question.md?key=semester_8%2Fsimulation_and_modeling%3Arn-properties-ks-algorithm) — Simulation and Modeling, chapter 6