0
2.5kviews
2015 6(a) binary search tree

What is Binary Search Tree (BST)? Construct a BST for the following numbers: 47, 55, 23, 17, 39, 11, 50, 9, 19, 74, 33, 28 Show all the steps. Write its preorder traversal

0
272views

## Binary Search Tree (BST)

• The binary search tree is an advanced algorithm of data structure that analyzes the node, its left, and right branches, and arranged in a tree structure format.
• Binary Search Tree (BST) follows the following two properties,
• The value of the key of the left sub-tree is less than the value of its parent (root) node's key.
• The value of the key of the right sub-tree is greater than or equal to the value of its parent (root) node's key.
• Basic operations performed by BST are search, insert, pre-order, in-order, and post-order traversal.

Features of BST:

• Nodes of the tree are represented in a parent-child relationship
• Each parent node can have zero child nodes or a maximum of two subnodes or subtrees on the left and right sides.
• Every sub-tree, also known as a binary search tree, has sub-branches on the right and left of themselves.
• All the nodes are linked with key-value pairs.
• The keys of the nodes present on the left subtree are smaller than the keys of their parent node
• Similarly, The left subtree nodes’ keys have lesser values than their parent node’s keys.
• The keys of the nodes present on the right subtree are greater than the keys of their parent node
• Similarly, The right subtree nodes’ keys have greater values than their parent node’s keys.

Binary Search Tree (BST) for the following sequence of numbers-

47, 55, 23, 17, 39, 11, 50, 9, 19, 74, 33, 28

Always consider the first element as the root node. Consider the given elements and insert them in the BST one by one.

This is the required Binary Seach Tree (BST).

## Preorder Traversal of BST

In preorder traversal, the root node is visited first, then the left subtree, and then finally the right subtree of BST.

Root Node ---> Left Subtree ---> Right Subtree

Hence, for the above Binary Search Tree Preorder Traversal sequence is like

47, 23, 17, 11, 9, 19, 39, 33, 28, 55, 50, 74