Fig. 1: A binary search tree of size 9 and depth 3, with 8 at the root. The leaves are not drawn.
In computer science, a binary search tree (BST), also called an ordered or sorted binary tree, is a rooted binary tree data structure with the key of each internal node being greater than all the keys in the respective node's left subtree and less than the ones in its right subtree. The time complexity of operations on the binary search tree is linear with respect to the height of the tree.
Binary search trees allow binary search for fast lookup, addition, and removal of data items. Since the nodes in a BST are laid out so that each comparison skips about half of the remaining tree, the lookup performance is proportional to that of binary logarithm. BSTs were devised in the 1960s for the problem of efficient storage of labeled data and are attributed to Conway Berners-Lee and David Wheeler.
The performance of a binary search tree is dependent on the order of insertion of the nodes into the tree since arbitrary insertions may lead to degeneracy; several variations of the binary search tree can be built with guaranteed worst-case performance. The basic operations include: search, traversal, insert and delete. BSTs with guaranteed worst-case complexities perform better than an unsorted array, which would require linear search time.
The complexity analysis of BST shows that, on average, the insert, delete and search takes O ( log n ) {\displaystyle O(\log n)} for n {\displaystyle n} nodes. In the worst case, they degrade to that of a singly linked list: O ( n ) {\displaystyle O(n)} . To address the boundless increase of the tree height with arbitrary insertions and deletions, self-balancing variants of BSTs are introduced to bound the worst lookup complexity to that of the binary logarithm. AVL trees were the first self-balancing binary search trees, invented in 1962 by Georgy Adelson-Velsky and Evgenii Landis.
Binary search trees can be used to implement abstract data types such as dynamic sets, lookup tables and priority queues, and used in sorting algorithms such as tree sort.
History
[
edit
]
The binary search tree algorithm was discovered independently by several researchers, including P.F. Windley, Andrew Donald Booth, Andrew Colin, Thomas N. Hibbard.[1][2] The algorithm is attributed to Conway Berners-Lee and David Wheeler, who used it for storing labeled data in magnetic tapes in 1960.[3] One of the earliest and popular binary search tree algorithm is that of Hibbard.[1]
The time complexities of a binary search tree increases boundlessly with the tree height if the nodes are inserted in an arbitrary order, therefore self-balancing binary search trees were introduced to bound the height of the tree to O ( log n ) {\displaystyle O(\log n)} .[4] Various height-balanced binary search trees were introduced to confine the tree height, such as AVL trees, Treaps, and red–black trees.[5]
The AVL tree was invented by Georgy Adelson-Velsky and Evgenii Landis in 1962 for the efficient organization of information.[6][7] It was the first self-balancing binary search tree to be invented.[8]
Overview
[
edit
]
A binary search tree is a rooted binary tree in which nodes are arranged in strict total order in which the nodes with keys greater than any particular node A is stored on the right sub-trees to that node A and the nodes with keys equal to or less than A are stored on the left sub-trees to A, satisfying the binary search property.[9]: 298 [10]: 287
Binary search trees are also efficacious in sortings and search algorithms. However, the search complexity of a BST depends upon the order in which the nodes are inserted and deleted; since in worst case, successive operations in the binary search tree may lead to degeneracy and form a singly linked list (or "unbalanced tree") like structure, thus has the same worst-case complexity as a linked list.[11][9]: 299-302
Binary search trees are also a fundamental data structure used in construction of abstract data structures such as sets, multisets, and associative arrays.
Operations
[
edit
]
Searching
[
edit
]
Searching in a binary search tree for a specific key can be programmed recursively or iteratively.
Searching begins by examining the root node. If the tree is nil, the key being searched for does not exist in the tree. Otherwise, if the key equals that of the root, the search is successful and the node is returned. If the key is less than that of the root, the search proceeds by examining the left subtree. Similarly, if the key is greater than that of the root, the search proceeds by examining the right subtree. This process is repeated until the key is found or the remaining subtree is nil {\displaystyle {\text{nil}}} . If the searched key is not found after a nil {\displaystyle {\text{nil}}} subtree is reached, then the key is not present in the tree.[10]: 290–291
Recursive search
[
edit
]
The following pseudocode implements the BST search procedure through recursion.[10]: 290
Recursive-Tree-Search(x, key)
if x = NIL or key = x.key then
return x
if key < x.key then
return Recursive-Tree-Search(x.left, key)
else
return Recursive-Tree-Search(x.right, key)
end if
The recursive procedure continues until a nil {\displaystyle {\text{nil}}} or the key {\displaystyle {\text{key}}} being searched for are encountered.
Iterative search
[
edit
]
The recursive version of the search can be "unrolled" into a while loop. On most machines, the iterative version is found to be more efficient.[10]: 291
Iterative-Tree-Search(x, key)
while x ≠ NIL and key ≠ x.key do
if key < x.key then
x := x.left
else
x := x.right
end if
repeat
return x
Since the search may proceed till some leaf node, the running time complexity of BST search is O ( h ) {\displaystyle O(h)} where h {\displaystyle h} is the height of the tree. However, the worst case for BST search is O ( n ) {\displaystyle O(n)} where n {\displaystyle n} is the total number of nodes in the BST, because an unbalanced BST may degenerate to a linked list. However, if the BST is height-balanced the height is O ( log n ) {\displaystyle O(\log n)} .[10]: 290
Successor and predecessor
[
edit
]
For certain operations, given a node x {\displaystyle {\text{x}}} , finding the successor or predecessor of x {\displaystyle {\text{x}}} is crucial. Assuming all the keys of the BST are distinct, the successor of a node x {\displaystyle {\text{x}}} in BST is the node with the smallest key greater than x {\displaystyle {\text{x}}} 's key. On the other hand, the predecessor of a node x {\displaystyle {\text{x}}} in BST is the node with the largest key smaller than x {\displaystyle {\text{x}}} 's key. Following is pseudocode for finding the successor and predecessor of a node x {\displaystyle {\text{x}}} in BST.[12][13][10]: 292–293
BST-Successor(x)
if x.right ≠ NIL then
return BST-Minimum(x.right)
end if
y := x.parent
while y ≠ NIL and x = y.right do
x := y
y := y.parent
repeat
return y
BST-Predecessor(x)
if x.left ≠ NIL then
return BST-Maximum(x.left)
end if
y := x.parent
while y ≠ NIL and x = y.left do
x := y
y := y.parent
repeat
return y
Operations such as finding a node in a BST whose key is the maximum or minimum are critical in certain operations, such as determining the successor and predecessor of nodes. Following is the pseudocode for the operations.[10]: 291–292
BST-Maximum(x)
while x.right ≠ NIL do
x := x.right
repeat
return x
BST-Minimum(x)
while x.left ≠ NIL do
x := x.left
repeat
return x
Insertion
[
edit
]
Operations such as insertion and deletion cause the BST representation to change dynamically. The data structure must be modified in such a way that the properties of BST continue to hold. New nodes are inserted as leaf nodes in the BST.[10]: 294–295 Following is an iterative implementation of the insertion operation.[10]: 294
1 BST-Insert(T, z) 2 y := NIL 3 x := T.root 4 while x ≠ NIL do 5 y := x 6 if z.key < x.key then 7 x := x.left 8 else 9 x := x.right 10 end if 11 repeat 12 z.parent := y 13 if y = NIL then 14 T.root := z 15 else if z.key < y.key then 16 y.left := z 17 else 18 y.right := z 19 end if
The procedure maintains a "trailing pointer" y {\displaystyle {\text{y}}} as a parent of x {\displaystyle {\text{x}}} . After initialization on line 2, the while loop along lines 4-11 causes the pointers to be updated. If y {\displaystyle {\text{y}}} is nil {\displaystyle {\text{nil}}} , the BST is empty, thus z {\displaystyle {\text{z}}} is inserted as the root node of the binary search tree T {\displaystyle {\text{T}}} , if it is not nil {\displaystyle {\text{nil}}} , insertion proceeds by comparing the keys to that of y {\displaystyle {\text{y}}} on the lines 15-19 and the node is inserted accordingly.[10]: 295
Deletion
[
edit
]
The nodeD {\displaystyle {\text{D}}}
The deletion of a node, say Z {\displaystyle {\text{Z}}} , from the binary search tree BST {\displaystyle {\text{BST}}} has three cases:[10]: 295-297
Z {\displaystyle {\text{Z}}}
Z {\displaystyle {\text{Z}}}
NIL {\displaystyle {\text{NIL}}}
Z {\displaystyle {\text{Z}}}
BST {\displaystyle {\text{BST}}}
Z {\displaystyle {\text{Z}}}
Z {\displaystyle {\text{Z}}}
Z {\displaystyle {\text{Z}}}
Z {\displaystyle {\text{Z}}}
Z {\displaystyle {\text{Z}}}
Z {\displaystyle {\text{Z}}}
Y {\displaystyle {\text{Y}}}
Z {\displaystyle {\text{Z}}}
Y {\displaystyle {\text{Y}}}
Z {\displaystyle {\text{Z}}}
Y {\displaystyle {\text{Y}}}
Z {\displaystyle {\text{Z}}}
Y {\displaystyle {\text{Y}}}
Y {\displaystyle {\text{Y}}}
Z {\displaystyle {\text{Z}}}
Z {\displaystyle {\text{Z}}}
Y {\displaystyle {\text{Y}}}
Z {\displaystyle {\text{Z}}}
The following pseudocode implements the deletion operation in a binary search tree.[10]: 296-298
1 BST-Delete(BST, D) 2 if D.left = NIL then 3 Shift-Nodes(BST, D, D.right) 4 else if D.right = NIL then 5 Shift-Nodes(BST, D, D.left) 6 else 7 E := BST-Successor(D) 8 if E.parent ≠ D then 9 Shift-Nodes(BST, E, E.right) 10 E.right := D.right 11 E.right.parent := E 12 end if 13 Shift-Nodes(BST, D, E) 14 E.left := D.left 15 E.left.parent := E 16 end if
1 Shift-Nodes(BST, u, v) 2 if u.parent = NIL then 3 BST.root := v 4 else if u = u.parent.left then 5 u.parent.left := v 5 else 6 u.parent.right := v 7 end if 8 if v ≠ NIL then 9 v.parent := u.parent 10 end if
The BST-Delete {\displaystyle {\text{BST-Delete}}} procedure deals with the 3 special cases mentioned above. Lines 2-3 deal with case 1; lines 4-5 deal with case 2 and lines 6-16 for case 3. The helper function Shift-Nodes {\displaystyle {\text{Shift-Nodes}}} is used within the deletion algorithm for the purpose of replacing the node u {\displaystyle {\text{u}}} with v {\displaystyle {\text{v}}} in the binary search tree BST {\displaystyle {\text{BST}}} .[10]: 298 This procedure handles the deletion (and substitution) of u {\displaystyle {\text{u}}} from BST {\displaystyle {\text{BST}}} .
Traversal
[
edit
]
A BST can be traversed through three basic algorithms: inorder, preorder, and postorder tree walks.[10]: 287
Following is a recursive implementation of the tree walks.[10]: 287–289
Inorder-Tree-Walk(x)
if x ≠ NIL then
Inorder-Tree-Walk(x.left)
visit node
Inorder-Tree-Walk(x.right)
end if
Preorder-Tree-Walk(x)
if x ≠ NIL then
visit node
Preorder-Tree-Walk(x.left)
Preorder-Tree-Walk(x.right)
end if
Postorder-Tree-Walk(x)
if x ≠ NIL then
Postorder-Tree-Walk(x.left)
Postorder-Tree-Walk(x.right)
visit node
end if
Balanced binary search trees
[
edit
]
Without rebalancing, insertions or deletions in a binary search tree may lead to degeneration, resulting in a height n {\displaystyle n} of the tree (where n {\displaystyle n} is number of items in a tree), so that the lookup performance is deteriorated to that of a linear search.[14] Keeping the search tree balanced and height bounded by O ( log n ) {\displaystyle O(\log n)} is a key to the usefulness of the binary search tree. This can be achieved by "self-balancing" mechanisms during the updation operations to the tree designed to maintain the tree height to the binary logarithmic complexity.[4][15]: 50
Height-balanced trees
[
edit
]
A tree is height-balanced if the heights of the left sub-tree and right sub-tree are guaranteed to be related by a constant factor. This property was introduced by the AVL tree and continued by the red–black tree.[15]: 50–51 The heights of all the nodes on the path from the root to the modified leaf node have to be observed and possibly corrected on every insert and delete operation to the tree.[15]: 52
Weight-balanced trees
[
edit
]
In a weight-balanced tree, the criterion of a balanced tree is the number of leaves of the subtrees. The weights of the left and right subtrees differ at most by 1 {\displaystyle 1} .[16][15]: 61 However, the difference is bound by a ratio α {\displaystyle \alpha } of the weights, since a strong balance condition of 1 {\displaystyle 1} cannot be maintained with O ( log n ) {\displaystyle O(\log n)} rebalancing work during insert and delete operations. The α {\displaystyle \alpha } -weight-balanced trees gives an entire family of balance conditions, where each left and right subtrees have each at least a fraction of α {\displaystyle \alpha } of the total weight of the subtree.[15]: 62
Types
[
edit
]
There are several self-balanced binary search trees, including T-tree,[17] treap,[18] red-black tree,[19] B-tree,[20] 2–3 tree,[21] and Splay tree.[22]
Examples of applications
[
edit
]
Sort
[
edit
]
Binary search trees are used in sorting algorithms such as tree sort, where all the elements are inserted at once and the tree is traversed at an in-order fashion.[23] BSTs are also used in quicksort.[24]
Priority queue operations
[
edit
]
Binary search trees are used in implementing priority queues, using the node's key as priorities. Adding new elements to the queue follows the regular BST insertion operation but the removal operation depends on the type of priority queue:[25]
See also
[
edit
]
References
[
edit
]
Further reading
[
edit
]
javinpaul
·
Follow
Published in
Javarevisited
·
8 min read
·
Apr 2, 2020
--
Hello guys, recently one of my readers was asked about how do you print all nodes of a binary search tree in sorted order during a telephonic Java interview. Unfortunately, he didn’t know that InOrder traversal can be used to print nodes in sorted order and he asked me after the interview.
In the past, I have shared the best data structure courses and data structure interview questions, and today, I will teach you about interesting and useful binary tree algorithms called InOrer traversal. We will also see an implementation using the Java programming language.
The InOrder traversal is one of the three popular ways to traverse a binary tree data structure, the other two being the preOrder and postOrder. During the in-order traversal algorithm, the left subtree is explored first, followed by root, and finally nodes on the right subtree.
You start traversal from the root then go to the left node, then again go to the left node until you reach a leaf node. At that point in time, you print the value of the node or mark it visited and move to the right subtree. Continuing the same algorithm until all nodes of the binary tree are visited.
The InOrder traversal is also known as the left-node-right or left-root-right traversal or LNR traversal algorithm.
Similar to the preOrder algorithm, it is also a depth-first algorithm because it explores the depth of a binary tree before exploring siblings. Since it is one of the fundamental binary tree algorithms it’s quite popular in programming interviews.
These traversal algorithms are also the basis to learn more advanced binary tree algorithms, hence every programmer should learn, understand, and know how to implement in-order and other traversal algorithms.
The easiest way to implement the inOrder traversal algorithm in Java or any programming language is by using recursion. Since the binary tree is a recursive data structure, recursion is the natural choice for solving a tree-based problem. The inOrder() the method in the BinaryTree class implements the logic to traverse a binary tree using recursion.
From the Interview point of view, InOrder traversal is extremely important because it also prints nodes of a binary search tree in the sorted order but only if a given tree is a binary search tree.
If you remember, in BST, the value of nodes in the left subtree is lower than the root, and the values of nodes on the right subtree are higher than the root. The In order traversal literally means IN order, I mean, nodes are printed in the order or sorted order.
Btw, even though these three algorithms (pre-order, in-order, and post-order) are popular binary tree traversal algorithms but they are not the only ones. You also have other breadth-first ways to traverse a binary tree, like level order traversal (See Data Structure and Algorithms: Deep Dive).
The recursive algorithm of inorder traversal is very simple. You just need to call the inOrder() method of BinaryTree class in the order you want to visit the tree. What is most important is to include the base case, which is key to any recursive algorithm.
For example, in this problem, the base case is you reach the leaf node and there is no more node to explore, at that point of time recursion starts to wind down. Here are the exact steps to traverse the binary tree using InOrder traversal:
private void inOrder(TreeNode node) {
if (node == null) {
return;
}inOrder(node.left);
System.out.printf("%s ", node.data);
inOrder(node.right);
}
Similar to the preOrder() method in the last example, there is another inOrder() method which exposes inorder traversal to the public and calls this private method which actually performs the InOrder traversal.
This is the standard way to write a recursive method which takes input, it makes it easier for a client to call the method.
public void inOrder() {
inOrder(root);
}
You can see that we start with root and then recursive call the inOrder() method with node.left, which means we are going down on left subtree until we hit node == null, which means the last node was a leaf node.
At this point in time, the inOrder() method will return and execute the next line, which prints the node.data. After that it's again a recursive inOrder() call with node.right, which will initiate the same process again.
You can also check out Data Structure and Algorithms Part 1 and 2 courses on Pluralsight to learn more about algorithms and how to design your own algorithms.
Btw, you would need a Pluralsight membership to access this course, which costs around $29 monthly or $299 annually (14% saving). I have one and I also suggest all developers have that plan because Pluralsight is like NetFlix for Software developers.
It has more than 5000+ good quality courses on all the latest topics. Since we programmers have to learn new things every day, an investment of $299 USD is not bad.
Btw, it also offers a 10-day free trial without any obligation which allows you to watch 200 hours of content. You can watch these courses for free by signing up for that 10-day free trial.