2015 6(a) binary search tree

269views

written 2.4 years ago by

binitamayekar ★ 6.4k

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.

BST 1 to 7

BST 8 to 11

BST 12 This is the required Binary Seach Tree (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

ADD COMMENT EDIT