## Data Structure Name: Binary Search Tree (BST) - #### Description: - A special form of binary tree where the value in each node must be greater than or equal to any values in its left subtree and less than or equal to any values in its right subtree - #### Variations: - #### Diagram: - #### General Use: ## Key Considerations - #### Properties: - Using in-order traversal ends up being in ascending order of values - #### Implementation Details: - Search - Return the node if the target value is equal to the value of the node - Continue searching in the left subtree if the target value is less than the value of the node - Continue searching in the right subtree if the target value is larger than the value of the node - Insertion - Search the left or right subtrees according to the relation of the value of the node and the value of our target node; - Repeat STEP 1 until reaching an external node; - Add the new node as its left or right child depending on the relation of the value of the node and the value of our target node. - Deletion - More complicated, one example solution: - If the target node has no child, we can simply remove the node. - If the target node has one child, we can use its child to replace itself. - If the target node has two children, replace the node with its in-order successor or predecessor node and delete that node. | | [[Big O - Time Complexity]] | [[Big O - Space Complexity]] | | ------ | ------------------------------- | ---------------------------- | | Access | | | | Add | O(h), where h is height of tree | | | Delete | O(h), where h is height of tree | | | Search | O(h), where h is height of tree | | - #### General Tips - #### Special Properties ## Specific Use Cases - TBD