Forum discussion on Binary Search Tree

Binary search tree

Binary search tree

by Sonnet Baidya -
Number of replies: 0


  • 11

    Notifications

     
    You have no notifications
  • f2?rev=3359775
Skip to main content

Answer for question-01

Binary Search Tree is a node-based binary tree data structure which has the following properties:

The left subtree of a node contains only nodes with keys lesser than the node’s key.The right subtree of a node contains only nodes with keys greater than the node’s key.The left and right subtree each must also be a binary search tree.

Answer for question-02

Binary search trees are better than linked lists or sorted arrays. Binary search can be used in many different settings, including an algorithm for search-problems and specific decision-making methods for optimization problems. Binary search requires maintaining a partial sequence of input data (usually it is sorted in sort order). The advantage we want outside of the algorithm is to access the position between each value at constant time. In a linked list, it may take time to get the position between [math] and (n) [/ math]. So the complexity of time will go from [mathematics] and (log-log {n}) [/ math] to [mathematics] and (n গ log} n}) [/ mathematics]. Data structures like arrays are much more suitable because you can slowly access any member of the array. Note that data must be selected to use a binary search

Data Structure and Lab

  1. Dashboard
  2. My courses
  3.  CSE134/135-MA
  4. Week 9: Discussion on Binary Search Tree (BST)
  5.  Forum discussion on Binary Search Tree
  6.  Answer
Search
Search forums
1

Forum discussion on Binary Search Tree

Answer

Display mode                     Display replies flat, with oldest first                     Display replies flat, with newest first                     Display replies in threaded form                     Display replies in nested form         
Picture of Sabbir Hossain Antar

Answer

by Sabbir Hossain Antar - Wednesday, 25 November 2020, 1:30 PM
Number of replies: 0
Picture of DS-(PC-E)

Answer 01

A Binary Search Tree (BST) is a tree in which all the nodes follow the below-mentioned 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.


Thus, BST divides all its sub-trees into two segments; the left sub-tree and the right sub-tree and can be defined as −


left_subtree (keys) < node (key) ≤ right_subtree (keys)



Answer 02

Binary search tree is better than linked list or sorted array.

Binary search is an algorithm for the search-problem, and can be utilized in many different settings, including certain kinds of decision procedures for optimization problems.

Binary search requires that the input data maintains a partial ordering (in simple terms, it is sorted in non-decreasing order). The benefit we want out of the algorithm is to access each value at the middle position in constant time. In a linked list, getting the middle position can take [math]O(n)[/math] time. So the time complexity would go from [math]O(\log{n})[/math] to [math]O(n\log{n})[/math].

A data structure such as an array is far more suitable as you can access any member of the array in constant time. Remember that the data must be sorted to use binary search.