Introduction to binary search tree in C

by

BST (Binary Search Tree) is a non-linear data structure known for its efficiency, offering a lower time complexity than linked lists or arrays when searching for a node.

In a Binary Search Tree, the left subtree always contains elements smaller than the root node, while the right subtree always contains elements greater than the root node. This structural property simplifies node searching and access, as one side of the subtree can be ignored.

Binary Search Tree Basics Generally, in a binary search tree, no two elements are equal. The binary tree is an ordered and sorted data structure.

Types of Traversal in Binary Search Tree: There are three types of traversal possible in a binary search tree:

  • Preorder – Root Left Right
  • In-order – Left Root Right
  • Postorder – Left Right Root
        21
       /  \
     14   28
     / \    / \
 11  18 25 32
  / \     /   / \
 5  12 15  31 33
            \
            19

Preorder Traversal: Starting with the root node (21 in this case), the traversal proceeds as follows:

  1. Root node 21
    • Recursively traverse the left subtree.
  2. Node 14
    • Traverse to the left subtree of 14.
  3. Node 11
    • Traverse to the left subtree of 11.
  4. Node 5
    • Since 5 has no child, traverse to the right subtree of 11.
  5. Node 12
    • Since 12 has no child, traverse to the right subtree of 14.
  6. Node 18
    • Traverse to the left subtree of 18.
  7. Node 15
    • Since 15 has no child, traverse to the right subtree of 18.
  8. Node 19
    • A new node.
  9. Traverse to the right side of the root node.
  10. Node 28
    • Traverse to the left subtree of 28.
  11. Node 25
    • Traverse to the left subtree of 25.
  12. Node 23
    • Since 23 has no child, traverse to the right subtree of 23.
  13. Node 26
    • Since 26 has no child, traverse to the right subtree of 28.
  14. Node 32
    • Traverse to the left subtree of 32.
  15. Node 31
    • Since 31 has no child, traverse to the right subtree of 32.
  16. Node 33
    • Preorder result: 21 14 11 5 12 18 15 19 28 25 23 26 32 31 33

Operations on BST:

  • Insert a Node
  • Search for a Node
  • Delete a Node

For more insightful posts, like our page and follow atomdyno.com. Share our articles with your friends.

Leave a Comment