Data Structures - lesson 4 | HackIndia Skills

Data Structures - lesson 4 | HackIndia Skills | HackIndia

Example

BST search code

Add this small Python file to your kit. Keep it boring and testable.

It shows the rule clearly: go left for smaller values, right for larger values.

# trees/bst_search.py

class Node:
    def __init__(self, val, left=None, right=None):
        self.val = val
        self.left = left
        self.right = right


def search(root, target):
    cur = root
    while cur:
        if cur.val == target:
            return True
        if target < cur.val:
            cur = cur.left
        else:
            cur = cur.right
    return False


def inorder(root):
    if not root:
        return []
    return inorder(root.left) + [root.val] + inorder(root.right)

Example

Test the rule

Your repo should prove code works. Add one test for search and one for sorted inorder traversal.

If you use pytest, this can go in tests/test_bst_search.py.

from trees.bst_search import Node, search, inorder


def sample_tree():
    return Node(
        8,
        Node(3, Node(1), Node(6)),
        Node(10, None, Node(14))
    )


def test_search_finds_existing_value():
    assert search(sample_tree(), 6) is True


def test_search_rejects_missing_value():
    assert search(sample_tree(), 7) is False


def test_inorder_is_sorted_for_bst():
    assert inorder(sample_tree()) == [1, 3, 6, 8, 10, 14]

Trees and BSTs

Core idea

When trees fit

BST costs

Common mistake

BST search code

Test the rule

Interview phrasing

Do this now

Quick check