Scribd
Upload
14 views8 pages

Dsa L12

A binary search tree (BST) is a binary tree where each node's left subtree contains values less than the node and the right subtree contains values greater than the node. Insertion into a BST follows a strategy based on comparing values with the current node, leading to potential performance issues if the tree becomes unbalanced. The worst-case performance of a BST can degrade to O(N) if it degenerates into a linked list.

Uploaded by

hiramanisahuc1
Copyright
© © All Rights Reserved
We take content rights seriously. If you suspect this is your content, claim it here.
Available Formats
Download as DOCX, PDF, TXT or read online on Scribd
14 views8 pages

Dsa L12

A binary search tree (BST) is a binary tree where each node's left subtree contains values less than the node and the right subtree contains values greater than the node. Insertion into a BST follows a strategy based on comparing values with the current node, leading to potential performance issues if the tree becomes unbalanced. The worst-case performance of a BST can degrade to O(N) if it degenerates into a linked list.

Uploaded by

hiramanisahuc1
Copyright
© © All Rights Reserved
We take content rights seriously. If you suspect this is your content, claim it here.
Available Formats
Download as DOCX, PDF, TXT or read online on Scribd

LEC12

Binary Search Trees


 A binary tree is a tree where each node has at most two children, referred to as the left
and right child
 A binary search tree is a binary tree in which every node's left subtree holds values
less than the root, and every right subtree holds values greater than the root's value.
 A new node is added as a leaf.

Binary Search Tree has some special properties: -

 Each element in the left subtree of an element is less than the root element of that
subtree.
 The left and right subtrees are themselves Binary Search Trees

50, 30, 12, 90, 100, 40, 94

Binary Search Tree (example)


Not a Binary Search Tree

Implementation of Binary Node

A binary search tree need not be full, complete or a two-tree, but it could be any of those
 If a binary search tree is full or complete, its height is logarithmic (base 2) in n
Drawback of BST: - Chain BST Search complexity is High.

Building a Binary Search Tree

Insertion strategy:

– If the value of the new element is less than the value of the current node, proceed to
the left subtree (left child) of the node. If null, insert the node as a left child of the
parent.
– If the value of the new element is greater than the value of the current node, proceed
to the right subtree (right child) of the node. If null, insert the node as a left child of
the parent.
Building a Binary Search Tree (continued): -

Insert value > root = Right Side


Insert value < root = Left Side

Question. Sample Insertion?


100, 164, 130, 189, 244, 42, 141, 231, 20, 153

Worst Case Performance


 In the worst case a BST can degenerate into a singly linked list.
 Performance goes to O(N)
 2 3 5 7 11 13 17
Adding to a Binary Search Tree
Searching a Binary Search Tree

Removing elements from a Binary Search Tree

You might also like