Binary Search Tree (Search and Insertion)
Binary Search Tree, is a node-based binary tree data structure.
Must have these properties for any Binary Search Tree:
1)The left sub tree of a node contains only nodes with keys less than the node’s key. 2)The right sub tree of a node contains only nodes with keys greater than the node’s key. 3)The left and right sub tree each must also be a binary search tree. 4)There should not be any duplicate nodes.
Now i have a question.why we will use BST(Binary Search Tree)?
Ans: Because Binary Search Tree provide an ordering among keys so that the operations like search, minimum and maximum can be done faster.
So searching is important.
Searching a key:
To search a given key in Binary Search Tree, we first compare it with root, if the key is present at root then we return root. If key is greater than root’s key then we recur for right sub-tree of root node. Otherwise we recur for left sub-tree.
Inserting a key:
A new key is always inserted at leaf. We start searching a key from root till we reach at-leaf node. Once a leaf node is found, the new node is added as a child of the leaf node.
Very important thing is what will be the complexity for this.Lets discuss on this.
Time Complexity:
In Worst Case,time complexity of search and insert operations is O(h)
where h is height of Binary Search Tree
Question is why?
here is the Answer: we may have to travel from root to the deepest leaf node.
The height of a skewed tree may become n and the time complexity of search and insert operation may become O(n).
Let me know any query till now.