Binary search tree: Difference between revisions

Revision as of 15:31, 18 June 2023

Revision as of 15:33, 18 June 2023

Line 200:

{{see also|Threaded binary tree}}

A BST can be [[Tree traversal|traversed]] through three basic algorithms: [[inorder traversal|inorder]], [[pre-order traversal|preorder]], and [[post-order traversal|postorder]] tree walks.<ref name="algo_cormen" />{{rp|287}}

*'''Inorder tree walk''': Nodes from the left subtree get visited first, followed by the root node and right subtree. In a BST, suchSuch a traversal visits all the nodes in the order of non-decreasing key sequence.

*'''Preorder tree walk''': The root node gets visited first, followed by left and right subtrees.

*'''Postorder tree walk''': Nodes from the left subtree get visited first, followed by the right subtree, and finally, the root. This can be used to delete a BST from the bottom (i.e., deleting children nodes first).

Following is a recursive implementation of the tree walks.<ref name="algo_cormen" />{{rp|287–289}}