BST Property and Why It Matters in DSA Rust

Mental Model

A Binary Search Tree keeps smaller values on the left and bigger values on the right, making it easy to find things fast.

Analogy: Think of a phone book where names are sorted alphabetically; you look left for names before 'M' and right for names after 'M'.

      5
     / \
    3   7
   / \   \
  2   4   8

Dry Run Walkthrough

Input: BST with nodes 5, 3, 7, 2, 4, 8; search for value 4

Goal: Show how BST property helps find 4 quickly by deciding left or right at each step

Step 1: Start at root node 5

      [5↑]
     /   \
    3     7
   / \     \
  2   4     8

Why: We begin search from the top of the tree

Step 2: Compare 4 with 5; 4 is less, go left

      5
     /   
    [3↑] 7
   / \     \
  2   4     8

Why: BST property says smaller values are on the left

Step 3: Compare 4 with 3; 4 is greater, go right

      5
     /   
    3     7
   /  [4↑]  \
  2         8

Why: BST property says bigger values are on the right

Step 4: Found node with value 4

      5
     /   
    3     7
   /    4↑  \
  2         8

Why: Search ends when value matches

Result:

      5
     /   
    3     7
   /    4↑  \
  2         8
Answer: Found 4

Annotated Code

DSA Rust

use std::rc::Rc;
use std::cell::RefCell;

#[derive(Debug)]
struct TreeNode {
    val: i32,
    left: Option<Rc<RefCell<TreeNode>>>,
    right: Option<Rc<RefCell<TreeNode>>>,
}

impl TreeNode {
    fn new(val: i32) -> Rc<RefCell<TreeNode>> {
        Rc::new(RefCell::new(TreeNode { val, left: None, right: None }))
    }
}

fn search_bst(root: Option<Rc<RefCell<TreeNode>>>, target: i32) -> Option<Rc<RefCell<TreeNode>>> {
    let mut current = root;
    while let Some(node_rc) = current.clone() {
        let node = node_rc.borrow();
        if target == node.val {
            return current; // found target
        } else if target < node.val {
            current = node.left.clone(); // go left
        } else {
            current = node.right.clone(); // go right
        }
    }
    None // not found
}

fn main() {
    // Build BST manually
    let root = TreeNode::new(5);
    let node3 = TreeNode::new(3);
    let node7 = TreeNode::new(7);
    let node2 = TreeNode::new(2);
    let node4 = TreeNode::new(4);
    let node8 = TreeNode::new(8);

    root.borrow_mut().left = Some(node3.clone());
    root.borrow_mut().right = Some(node7.clone());
    node3.borrow_mut().left = Some(node2.clone());
    node3.borrow_mut().right = Some(node4.clone());
    node7.borrow_mut().right = Some(node8.clone());

    let target = 4;
    let result = search_bst(Some(root.clone()), target);

    match result {
        Some(node) => println!("Found {}", node.borrow().val),
        None => println!("{} not found", target),
    }
}

while let Some(node_rc) = current.clone() {

loop through nodes until we find target or reach end

if target == node.val {

check if current node is target

current = node.left.clone();

go left if target smaller than current node

current = node.right.clone();

go right if target bigger than current node

Output

Found 4

Complexity Analysis

Time: O(h) where h is tree height, because we follow one path down the tree

Space: O(1) because we only keep track of current node during search

vs Alternative: Compared to searching an unsorted tree or list (O(n)), BST search is faster if tree is balanced

Edge Cases

Empty tree

Search returns None immediately

DSA Rust

while let Some(node_rc) = current.clone() {

Target not in tree

Search reaches a leaf and returns None

DSA Rust

while let Some(node_rc) = current.clone() {

Target is root value

Search returns root immediately

DSA Rust

if target == node.val {

When to Use This Pattern

When you need to quickly find or check values in a sorted tree, look for the BST property to guide your search efficiently.

Common Mistakes

Mistake: Not comparing target with current node value to decide left or right
Fix: Always compare target with current node value to choose correct subtree

Summary

It keeps smaller values left and bigger values right to speed up search.

Use it when you want fast lookup, insert, or delete in sorted data.

The key is comparing target with current node to decide direction.

Practice

1. What is the main property that defines a Binary Search Tree (BST)?

easy

A. For each node, all values in the left subtree are smaller, and all values in the right subtree are larger.

B. Each node has exactly two children.

C. All leaf nodes are at the same depth.

D. Nodes are arranged in a complete binary tree structure.

Solution

1. Step 1: Understand BST definition

   A BST requires that for every node, values in the left subtree are smaller and values in the right subtree are larger.

2. Step 2: Compare options to BST property

   For each node, all values in the left subtree are smaller, and all values in the right subtree are larger. matches this definition exactly, while others describe different tree types or properties.

3. Final Answer:

   For each node, all values in the left subtree are smaller, and all values in the right subtree are larger. -> Option A

4. Quick Check:

   BST property = For each node, all values in the left subtree are smaller, and all values in the right subtree are larger. [OK]

Hint: Remember: left < node < right in BST [OK]

Common Mistakes:

• Confusing BST with complete binary tree
• Thinking all nodes must have two children
• Assuming leaf nodes must be at same depth

2. Which Rust code snippet correctly declares a BST node struct with optional left and right children?

easy

A. struct Node { value: i32, left: Option<Node>, right: Option<Node> }

B. struct Node { value: i32, left: Option, right: Option }

C. struct Node { value: i32, left: Box<Node>, right: Box<Node> }

D. struct Node { value: i32, left: Node, right: Node }

Solution

1. Step 1: Understand Rust ownership and recursive types

   Recursive structs in Rust must use Box to allocate on heap and Option for nullable children.

2. Step 2: Check each option

   struct Node { value: i32, left: Option, right: Option } uses Option correctly. Using Node directly or Option<Node> (without Box) causes infinite size. struct Node { value: i32, left: Box<Node>, right: Box<Node> } misses Option, so children can't be null.

3. Final Answer:

   struct Node { value: i32, left: Option, right: Option } -> Option B

4. Quick Check:

   Use Option for nullable recursive fields [OK]

Hint: Use Option for nullable recursive nodes in Rust [OK]

Common Mistakes:

• Omitting Option for nullable children
• Using Node directly causing infinite size error
• Not boxing recursive fields

3. Given the following Rust code inserting values into a BST, what is the in-order traversal output?

struct Node { value: i32, left: Option, right: Option }

fn insert(root: &mut Option, val: i32) {
    match root {
        None => *root = Some(Box::new(Node { value: val, left: None, right: None })),
        Some(node) => {
            if val < node.value {
                insert(&mut node.left, val);
            } else {
                insert(&mut node.right, val);
            }
        }
    }
}

fn inorder(root: &Option, vals: &mut Vec<i32>) {
    if let Some(node) = root {
        inorder(&node.left, vals);
        vals.push(node.value);
        inorder(&node.right, vals);
    }
}

fn main() {
    let mut root = None;
    insert(&mut root, 10);
    insert(&mut root, 5);
    insert(&mut root, 15);
    insert(&mut root, 7);
    let mut result = Vec::new();
    inorder(&root, &mut result);
    println!("{:?}", result);
}

medium

A. [5, 7, 10, 15]

B. [10, 5, 7, 15]

C. [15, 10, 7, 5]

D. [7, 5, 10, 15]

Solution

1. Step 1: Insert values into BST

   Insert 10 as root, 5 to left, 15 to right, 7 to right of 5.

2. Step 2: Perform in-order traversal

   In-order visits left subtree, node, then right subtree. So order is 5, 7, 10, 15.

3. Final Answer:

   [5, 7, 10, 15] -> Option A

4. Quick Check:

   In-order traversal of BST = sorted values [OK]

Hint: In-order traversal of BST gives sorted values [OK]

Common Mistakes:

• Confusing traversal order
• Inserting nodes incorrectly
• Assuming pre-order or post-order output

4. The following Rust function is intended to check if a tree is a valid BST. What is the bug?

fn is_bst(node: &Option, min: i32, max: i32) -> bool {
    match node {
        None => true,
        Some(n) => {
            if n.value <= min || n.value >= max {
                return false;
            }
            is_bst(&n.left, min, n.value) && is_bst(&n.right, n.value, max)
        }
    }
}

medium

A. The function should return false when node is None.

B. The function does not handle empty trees correctly.

C. The min and max parameters are not updated correctly during recursion.

D. The comparison uses <= and >= instead of < and >, disallowing duplicate values.

Solution

1. Step 1: Analyze comparison operators

   The function uses <= and >= which disallow equal values, meaning duplicates are not allowed.

2. Step 2: Understand BST duplicate handling

   Some BST definitions allow duplicates on one side (usually right). Using strict < and > allows duplicates on one side.

3. Final Answer:

   The comparison uses <= and >= instead of < and >, disallowing duplicate values. -> Option D

4. Quick Check:

   Use < and > to allow duplicates in BST check [OK]

Hint: Use strict < and > to allow duplicates in BST check [OK]

Common Mistakes:

• Thinking None nodes cause errors
• Believing min/max are updated incorrectly
• Assuming empty tree is invalid

5. You want to find the kth smallest element in a BST efficiently. Which approach best uses the BST property to achieve this?

hard

A. Convert the BST to a sorted array and then access the kth element.

B. Perform a pre-order traversal and count nodes until k is reached.

C. Perform an in-order traversal and return the kth element visited.

D. Traverse the tree level by level until the kth node is found.

Solution

1. Step 1: Recall BST in-order traversal property

   In-order traversal visits nodes in ascending order due to BST property.

2. Step 2: Use in-order traversal to find kth smallest

   Counting nodes during in-order traversal lets you stop at kth smallest efficiently without extra sorting.

3. Final Answer:

   Perform an in-order traversal and return the kth element visited. -> Option C

4. Quick Check:

   In-order traversal gives sorted order, find kth element [OK]

Hint: Use in-order traversal to get sorted nodes and pick kth [OK]

Common Mistakes:

• Using pre-order or level-order which are not sorted
• Converting to array wastes extra space
• Not leveraging BST property for efficiency