# Binary Search Trees Source: https://wisconsin.twango.dev/fa24-cs300/u5-hierarchical-data/binary-search-trees # Binary Search Trees ## Trees A tree is a data structure that consists of nodes connected by edges. Each node has a parent node (except for the root) and zero or more child nodes. The top node of a tree is called the root node, and nodes with no children are called leaf nodes. Trees are used to represent hierarchical relationships between elements, such as file systems, organization charts, and family trees. They are also used to implement more complex data structures, such as binary search trees and heaps. ![[u5-hierarchical-data/tree.png]] ### Traversal #### In Order In-order traversal of a binary tree visits the nodes in the following order: 1. Traverse the left subtree. 2. Visit self. 3. Traverse the right subtree. > [!tip] > In-order traversal of a binary search tree (BST) visits the nodes in ascending order. #### Pre Order Pre-order traversal of a binary tree visits the nodes in the following order: 1. Visit self. 2. Traverse the left subtree. 3. Traverse the right subtree. #### Post Order Post-order traversal of a binary tree visits the nodes in the following order: 1. Traverse the left subtree. 2. Traverse the right subtree. 3. Visit self. ## Binary Trees A binary tree is a tree data structure in which each node has at most two children, referred to as the left child and right child. Binary trees are used to implement binary search trees, expression trees, and other tree-based data structures. > [!example] > ```mermaid > graph TD > A > A --> B > A --> C > B --> D > B --> E > C --> F > C --> G > ``` ### Binary Search Trees A binary search tree (BST) is a binary tree in which each node has a key value and satisfies the following properties: 1. The left subtree of a node contains only nodes with keys less than the node's key. 2. The right subtree of a node contains only nodes with keys greater than the node's key. 3. The left and right subtrees are also binary search trees. ```mermaid graph TD 15 15 --> 10 15 --> 20 10 --> 8 10 --> 12 20 --> 17 20 --> 25 ``` BSTs are used to implement efficient search, insert, and delete operations. The time complexity of these operations is $O(\log N)$ on average, where $N$ is the number of nodes in the tree. > [!note] > The time complexity of search, insert, and delete operations on a BST is $O(N)$ in the worst case when the tree is unbalanced. > > A maximally skewed tree has height $N-1$ when height counts edges, where $N$ is the number of nodes. To maintain the $O(\log N)$ time complexity, the tree must be balanced. > > AVL and red-black trees maintain height bounds. Splay trees provide amortized performance guarantees but need not remain height-balanced. > [!question]- Are BSTs valid if there are only left or right children? > Yes, a BST is valid even if there are only left or right children. The key property of a BST is that the left subtree contains nodes with keys less than the node's key, and the right subtree contains nodes with keys greater than the node's key. Thus, the BST property is maintained even if there are only left or right children. > > However, trees with only left or right children are not balanced and can lead to $O(N)$ time complexity for search, insert, and delete operations in the worst case. #### Operations BSTs support the following operations: - **Search**: Find a node with a given key. - **Insert**: Insert a new node with a given key. - **Delete**: Remove a node with a given key. - **Height**: Calculate the height of the tree. ##### Search To search for a key in a BST, we start at the root node and compare the key with the root's key. If the key is less than the root's key, we search the left subtree. If the key is greater than the root's key, we search the right subtree. We continue this process until we find the key or reach a leaf node. The time complexity of the search operation is $O(\log N)$ on average and $O(N)$ in the worst case. #### Pseudocode ```text search(node, key): if node is null or node.key is equal to key: return node if key is less than node.key: return search(node.left, key) return search(node.right, key) ``` #### Java ```java public Node search(Node node, int key) { if (node == null || node.key == key) { return node; } if (key < node.key) { return search(node.left, key); } return search(node.right, key); } ``` ##### Insert To insert a new key into a BST, we search for the appropriate position to insert the key. If the key is less than the current node's key, we insert it in the left subtree. If the key is greater than the current node's key, we insert it in the right subtree. We continue this process until we find an empty position to insert the key. The time complexity of the insert operation is $O(\log N)$ on average and $O(N)$ in the worst case. #### Pseudocode ```text insert(node, key): if node is null: return new Node(key) if key is less than node.key: node.left = insert(node.left, key) else if key is greater than node.key: node.right = insert(node.right, key) return node ``` #### Java ```java public Node insert(Node node, int key) { if (node == null) { return new Node(key); } if (key < node.key) { node.left = insert(node.left, key); } else if (key > node.key) { node.right = insert(node.right, key); } return node; } ``` ##### Delete To delete a key from a BST, we first search for the key to be deleted. If the key is found, we handle three cases: 1. The node has no children: We simply remove the node. 2. The node has one child: We replace the node with its child. 3. The node has two children: We find the node with the minimum key in the right subtree (or the node with the maximum key in the left subtree), copy its key to the node to be deleted, and delete the node with the minimum key. The time complexity of the delete operation is $O(\log N)$ on average and $O(N)$ in the worst case. #### Pseudocode ```text delete(node, key): if node is null: return node if key is less than node.key: node.left = delete(node.left, key) else if key is greater than node.key: node.right = delete(node.right, key) else: if node has no left child: return node.right if node has no right child: return node.left temp = findMin(node.right) node.key = temp.key node.right = delete(node.right, temp.key) return node ``` #### Java ```java public Node delete(Node node, int key) { if (node == null) { return node; } if (key < node.key) { node.left = delete(node.left, key); } else if (key > node.key) { node.right = delete(node.right, key); } else { if (node.left == null) { return node.right; } if (node.right == null) { return node.left; } Node temp = findMin(node.right); node.key = temp.key; node.right = delete(node.right, temp.key); } return node; } ``` > [!tip] > To find the node with the minimum key in a subtree, we traverse the left subtree until no left child remains; the minimum node may still have a right child. > > #### Pseudocode > > ```text > findMin(node): > while node.left is not null: > node = node.left > return node > ``` > > #### Java > > ```java > public Node findMin(Node node) { > while (node.left != null) { > node = node.left; > } > return node; > } > ``` ##### Height The height of a binary tree is the maximum depth of the tree, i.e., the length of the longest path from the root node to a leaf node. The height of an empty tree is $-1$, and the height of a tree with a single node is $0$. The time complexity of calculating the height of a binary tree is $O(N)$, where $N$ is the number of nodes in the tree. #### Pseudocode ```text height(node): if node is null: return -1 leftHeight = height(node.left) rightHeight = height(node.right) return 1 + max(leftHeight, rightHeight) ``` #### Java ```java public int height(Node node) { if (node == null) { return -1; } int leftHeight = height(node.left); int rightHeight = height(node.right); return 1 + Math.max(leftHeight, rightHeight); } ``` ## Source The existing course note was retained and normalized during the merge. Related: [[u5-hierarchical-data/index|Topic index]].