A binary tree in which, for every node, all values in the left subtree are smaller and all values in the right subtree are larger than the node. Search, insertion and deletion take time proportional to the tree's height, and an in-order traversal visits the values in ascending order.
Japanese name: 二分探索木
Binary search tree appears in 4 practice questions across 1 topic, including Data Structures and Algorithms.
A search starts at the root and moves to the left child if the target is smaller than the node or to the right child if it is larger, repeating until it finds a match or runs out of children. Insertion searches and attaches a new node where the search ran out of children. Deletion removes a node with zero or one child and reconnects the child; a node with two children is replaced by the smallest value in its right subtree (or the largest in its left subtree), and that node is deleted instead. Every operation takes time proportional to the number of levels from the root to a leaf (the tree's height).
A binary search tree with n nodes has a height of about log₂ n if it is balanced, but inserting values in sorted order, such as 1, 2, 3, …, produces a single chain extending to one side with height n−1. Searching it then takes O(n), the same as a linked list. AVL trees and red-black trees are self-balancing binary search trees that reshape themselves with operations called rotations on every insertion and deletion, keeping the height at O(log n); they are used for the ordered dictionaries and sets of many programming languages.
Ways of visiting every node of a tree include pre-order, which visits each node first; in-order, which visits the left subtree, the node and then the right subtree; post-order, which visits the children first; and breadth-first (level-order), which visits the tree level by level. An in-order traversal of a binary search tree lists the values in ascending order, giving a sorted listing. A post-order traversal of an expression tree gives Reverse Polish notation.
Answer: A. In ascending order (smallest first)
In a binary search tree, for every node, all values in the left subtree are smaller than the node and all values in the right subtree are larger. Visiting the left subtree, the node and then the right subtree therefore visits the values from smallest to largest, so the result is in ascending order. Visiting nodes in order of closeness to the root is a breadth-first (level-order) traversal, which goes level by level from left to right. The insertion order affects the shape of the tree but does not match the order of any of these traversals.
Answer: B. 20, 40, 30, 60, 80, 70, 50
The root is 50; its left child is 30 (with children 20 and 40) and its right child is 70 (with children 60 and 80). Post-order visits the left subtree as 20, 40, 30 and the right subtree as 60, 80, 70, and only then the root 50. 50, 30, 20, 40, 70, 60, 80 is the pre-order result, which visits each node first, and 20, 30, 40, … is the in-order result. Post-order is used when children must be processed first, such as when deleting a tree or producing postfix notation from an expression tree.
A binary search tree follows the rule “smaller on the left, larger on the right”, so it can search for any value and list values in order. A binary heap only follows the rule “a parent is larger (or smaller) than its children”, so it can quickly remove the maximum (or minimum) but is not suited to searching for arbitrary values.
In memory, self-balancing binary search trees are used; for storage read in blocks, such as disks and SSDs, B-trees (B+ trees), which keep the tree shallow by putting many keys in each node, are used.
In a binary search tree, for every node, all values in the left subtree are smaller than the node and all values in the right subtree are larger.
When a binary search tree is traversed in in-order (visitin…A balanced tree would have only about log₂ 1000 ≈ 10 levels, so using a self-balancing binary search tree such as an AVL tree or a red-black tree, which reshapes itself on every insertion and deletion, keeps the worst case at O(log n).
The values 1, 2, 3, …, 1000 are inserted in this order into…A binary search tree with 100 million records needs at least about 27 levels, and reading a different block at each level is slow.
What is the main reason that B-trees (including B+ trees), …As an Amazon Associate I earn from qualifying purchases.
Linked list Binary heap Binary search Breadth-first search Depth-first search Dijkstra's algorithm Dynamic programming Greedy algorithm Hash table Queue