Binary Search Tree

Binary Search Tree Advance Data Structure

1. Binary Search Tree

2. We’ll discuss the following Content today: 01 Binary Search Tree Definition 02 Properties of Binary Tree How to search a binary search tree? 03 Pseudo code Complexities Examples Resources

3. Binary Search Tree Definition The Binary Tree is a Tree. In which every parent node have maximum two child nodes. A Binary Search Tree is a variation of Binary Search Tree. The values in the Binary Search tree can be stored in the specific sequence. It is called a search tree because it can be used to search for the presence of a number in O(Log(n) times. A Binary Search Tree is an ordered tree. There is no permission for duplicate nodes.

4. Properties of Binary Search Tree The properties that separate a binary search tree from a regular binary tree is: All nodes of left sub tree are less than the root node. All nodes of right sub tree are more than the root node. Both sub trees of each node are also BSTs i.e. they have the above two properties. 8 6 5 9 10 7 Root

5. Properties of Binary Search Tree 8 3 1 6 4 8 3 1 6 2 The binary tree on the right side isn't a binary search tree because the right subtree of the node "3" contains a value smaller than it.

6. How to search a binary search tree? 17 15 18 6 3 7 13 13 4 9 20 Root (1) Start at the root (2) Compare the value of the item you are searching for with the value stored at the root (3) If the values are equal, then item found ; otherwise, if it is a leaf node, then not found. (4) If it is less than the value stored at the root, then search the left sub tree. (5) If it is greater than the value stored at the root, then search the right sub tree. (6) Repeat steps 2-6 for the root of the sub tree chosen in the previous step 4 or 5. We have to Search 9: Compare 9 with 15 Compare 9 with 6 Compare 9 with 7 Compare 9 with 13 Compare 9 with 9 Hurray Value Find Is this better than searching a linked list? Yes !! ---> O( logN )

7. Time Complexities Operation Best Case Complexity Average Case Complexity Worst Case Complexity Search O(log n) O(log n) O(n) Insertion O(log n) O(log n) O(n) Deletion O(log n) O(log n) O(n) Space Complexity The space complexity for all the operations is  O(n). Note: Here,  n  is the number of nodes in the tree.

8. Applications In multilevel indexing in the database For dynamic sorting For managing virtual memory areas in Unix kernel

9. https://www.programiz.com/dsa/binary-search-tree https://en.wikipedia.org/wiki/Binary_search_tree https://www.upgrad.com/blog/difference-between-binary-tree-and-binary-search-tree/ Resources

10. Thanks