Binary Search Tree and Traversals - Piyu's CS

Binary Search Tree and Traversals

A Binary Search Tree (BST) is a binary tree with an additional ordering property:

BST Property :

For each node x in the tree:

All nodes in the left subtree of x have values less than x’s key.
All nodes in the right subtree of x have values greater than x’s key.
Both left and right subtrees must also be BSTs.

Binary Search Tree Traversals

1. Inorder Traversal

Visits nodes in sorted (ascending) order for a BST.
Algorithm:
1. Recursively traverse the left subtree.
2. Visit the root node.
3. Recursively traverse the right subtree.

2. Preorder Traversal

Visits the root first, then left and right subtrees.
Used in copying a tree or prefix notation evaluation.
Algorithm:
1. Visit the root node.
2. Recursively traverse the left subtree.
3. Recursively traverse the right subtree.

3. Postorder Traversal

Visits the left subtree, then right, and finally the root.
Used in deleting a tree or postfix notation evaluation.
Algorithm:
1. Recursively traverse the left subtree.
2. Recursively traverse the right subtree.
3. Visit the root node.