Tree


  • Overview of Trees
  • Terminologies
  • Types of Trees
  • Tree Traversals
  • Traversals-Illustration
  • Binary Trees
  • Types of Binary Trees
  • Implementation in Python
  • Binary Tree Traversals
  • Implementation of Binary Trees
  • Applications of Binary trees
  • Binary Search Trees
  • Implementation Of BST

    • Practice Questions

    Binary Search Trees

    Binary Search Tree is a special case of Binary Tree , where the elements have some kind of order. The order is ,

    • 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.
    • Elements are not duplicated , elements are always unique.
    • If you take any node, for eg: 10 , the nodes on the left of 10 are smaller than 10.

    • The nodes on the right of 10 are greater than 10.

      Similarly we can take any node and check . Always the nodes on the left of the particular node will be smaller and the nodes on the right side of the particular node will be greater than the node in question.

      Searching :

      In the above tree, if you want to search for the number 6, we can start from the root node 10, and since 6 is less than 10, we are sure that 6 will be on the left sub tree (on the left side of 10).

      So ,now under 10 , we have child node 5. Our search 6 is greater than 5, so we should look for the right child of 5. 

      Bingo ! we got 6.

       

      Search Complexity :

      In every iteration, we reduce the search complexity by ½ space.

      For eg; when we searched for 6, since it is smaller than the root node 10, we eliminated searching on the right sub tree. 

      In every iteration, we reduce search space by ½.

      Say if we have 8 nodes, n=8.   8 →4→2→1

      We have to do only 3 iterations.

      log₂8=3.

      So,Search Complexity can be said as ,

      Search Complexity = O (log n)
       

      Advantages of Binary Search Trees:

    • Binary Search Tree is very fast in Insertion and Deletion operations etc , when the tree is balanced.
    • Binary Search Tree is very efficient and its code is easier when compared to linked list code.
    • Duplicate keys or elements are not allowed in the Binary Search Tree.

    • Disadvantages of Binary Search Trees:

    • The Shape of the BST totally depends on the order of Insertions and it can be regenerated for the same key elements , we can get a different shape BST.
    • It takes a long time to search an element in a BST because key value of each node has to be compared with the key element to be searched.
    • Height of  BST is not under control because it depends on how elements are inserted

    Try here>>>