gen-define-a-binary-search-tree-and-give-one-short-worked-exampl-1aa7

Define a binary search tree and give one short worked example.

# Binary Search Tree (BST) ## Definition A **Binary Search Tree** is a binary tree data structure where each node contains a value and has at most two children (left and right), with the following property: - All values in the **left subtree** are **less than** the node's value - All values in the **right subtree** are **greater than** the node's value - Both left and right subtrees are also binary search trees ## Worked Example **Task:** Insert the values `[5, 3, 7, 1, 4, 6, 9]` into a BST in that order. **Step-by-step construction:** ``` Insert 5: 5 Insert 3 (3 < 5, go left): 5 / 3 Insert 7 (7 > 5, go right): 5 / \ 3 7 Insert 1 (1 < 5, go left; 1 < 3, go left): 5 / \ 3 7 / 1 Insert 4 (4 < 5, go left; 4 > 3, go right): 5 / \ 3 7 / \ 1 4 Insert 6 (6 > 5, go right; 6 < 7, go left): 5 / \ 3 7 / \ / 1 4 6 Insert 9 (9 > 5, go right; 9 > 7, go right): 5 / \ 3 7 / \ / \ 1 4 6 9 ``` **Result:** A valid BST where in-order traversal (1, 3, 4, 5, 6, 7, 9) gives sorted values.