BST – Set 1

BST Visualizer
In a complete(almost)  binary tree number of nodes (n) and height of tree (h) have a relationship like => n = 2^(h+1) -1,   this is the all the nodes of the tree.
If we have n nodes in a complete(almost) BT then height of the tree will be floor(log(n)),
(base 2) this is derived from the above condition.
A complete binary tree is a binary tree in which every level, except possibly the last, is completely filled, and all nodes are as far left as possible.
Balanced Tree  – A BST is balanced if height of left and right subtree differ by 1 and both left and right subtree are BST.

  1. Binary Search Tree – insertion, search  Code GFG
     – A new key is always inserted at leaf.
    –  Inorder traversal of BST always produces sorted output.
    –  We can construct a BST with only Preorder or Postorder or Level Order traversal.     Note that we can always get inorder traversal by sorting the only given traversal.
    Time Complexity: The worst case time complexity of search and insert operations is O(h) where h is height of Binary Search Tree. In worst case, 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).SO   Complexity to create BST  depends how do you construct this tree. If you do not know all the elements of BST in advance then you have to insert each of n elements one after another.  Average case – To insert n elements into a binary tree it’s O(nlog(n)). 
    If you are extremely unlucky (skewed tree), the complexity of insert is O(n) and thus it deteriorates to O(n^2).Notice that this situation is highly unlikely, but still possible. But you can still achieve O(nlog(n)) if you know all the elements in advance. You can sort them O(nlog(n)) and then insert the elements in the following order. Take the middle element and insert it as a root, then recursively do the same for both parts that are left. You will end up creating balanced BST, inserting n elements using log(n).


  2. Binary Search Tree – Deletion  Code  GFG
    Algo: Three cases to handle –
    1) Node to be deleted is leaf: Simply remove from the tree.
    2) Node to be deleted has only one child: Copy the child to the node and delete the child
    3) Node to be deleted has two children –  Find inorder successor of the node(next smallest element in the tree). Copy contents of the inorder successor to the node and delete the inorder successor. Note that inorder predecessor can also be used.
    While coding this, case 1 and 2 are combined.
    Time Complexity: The worst case time complexity of delete operation is O(h) where h is height of Binary Search Tree. In worst case, 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 delete operation may become O(n)


  3. *** Data Structure for a single resource reservations. This forms a class of problem which pertain to allocating resources like in a system, or allocating lane for landing of plane at airport. This is always given with few constraint. GFG
    One way to approach this problem is to maintain a sorted array.
    A better way is to implement this using a BST. Like for the above question, when we need to check if a  resource can be allocated at time t, where we know that each task k times. Our node value will be this t.
    When we need to allocate resource we check if  resource is already allocated in t-k and t+k time(this is given as a constraint). Now if we find any such node, then the resource can’t be allocated else it can be.
    In a real system we will also have come way to update the BST to remove the jobs that have been completed(like a polling system).
    — Plus we also need to consider the current time of the system, T, if t < T, then the job can’t be allocated resource as the time has already passed.


  4. Minimum value in a BST – GFG
    Algo: Unlike a BT we now that the smallest value will exists only in the left tree. So we keep checking only the left subtree. The last node will be the smallest value.


  5. *** Inorder predecessor and successor for a given key in BST. GFG. Code
    Algo:  If key is smaller then root node, set the successor as root else set the predecessor as root. When the key is located then we need to check for it’s predessor and successor. Predecessor will be maximum element in the left subtree of that node.  Successor will be the minimum element in the right subtree.
    Similar: Floor and Ceil from a BST. GFG Code


  6. **** Check if a binary tree is BST or notGFG
    Check the incorrect solution. Just check each node for BST is an incorrect solution. It won’t satisfy case like the one below.tree_bst
    1. The idea is to traverses down the tree keeping track of the narrowing min and max allowed values as it goes, looking at each node only once. We basically set a range within which each node value can lies depending on the previous node value.
    Time Complexity: O(n). Youtube
    2. Do an Inorder traversal and store all the element in an array. Then check if the array is sorted correctly.  We don’t actually need to store all the element, we can just keep track of the last element and if the next element being entered is smaller then the last one then break. Code
    Time Complexity: O(n)


  7. *** Advantages of BST over Hash Table. 
    We can get all keys in sorted order by just doing Inorder Traversal of BST.
    — Doing order statisticsfinding closest lower and greater elementsdoing range queries are easy to do with BSTs.
    — BSTs are easy to implement compared to hashing, we can easily implement our own customized BST. To implement Hashing, we generally rely on libraries provided by programming languages
    — With BSTs, all operations are guaranteed to work in O(Logn) time. But with Hashing, Θ(1) is average time and some particular operations may be costly, especially when table resizing happens.


  8. *** LCA in BST – Code GFG
    Algo: T
    he main difference in finding LCA in BT and BST is lies in there fundamental. BST is organized. So if both the values lies on either side of a node(or say root of a subtree), that will be the LCA.


  9. Sorted order printing of a given array that represents a BST Given an array that stores a Complete Binary Search Tree, write a function that efficiently prints the given array in ascending order. GFG
    Array representation of a binary tree is actually level order.
    –   When a binary tree is represented as array, the left child of index i is (2*i)+1 and its right child is at (2*i)+2 index. The inorder traversal using this information and get the sorted order output.
    Direct sorting is definitely an option. The time complexity of sorting will be at least O(nLogn).


  10. *** Find k-th smallest element in BST (Order Statistics in BST).
    can be presented like – Second largest element in BST
    1. GFGCode O(n). Do a inorder traversal and have a counter till k.
    2. There’s an O(h) solution for the same. SO
    3. GFG Do a reverse inorder traversal. First move to the rightmost node(which will be the largest element) then start counting the number of elements elapsed to get the kth element.Time complexity: The code first traverses down to the rightmost node which takes O(h) time, then traverses k elements in O(k) time. Therefore overall time complexity is O(h + k). Worst case is still O(n).
    Similar: Largest and Second largest- Code Recursive Code Iterative


  11. [Pending]  K’th smallest element in BST using O(1) Extra Space. Morris Traversal GFG

  12. Print BST keys in the given range. GFG Straightforward.

  13. **** Sorted Array to Balanced BST. GFG. Code. Asked in Amazon, Cisco
    Algo: Since it’s a balanced binary tree we try to divide all the element on both side equally, find populating the left tree. We divide the array into two part, using mid. Then do the same recursively for the left and right array.
    Read this


  14. **** Largest BST in BT. Youtube . Code
    Algo: We will use a part of the logic to check if a BT is a BST as we need to identify each subtree individually(we need to narrow down the range of possible values). We need to start with the smallest node and keep checking the size of the maximum BST till that node.


  15. [Pending] Check for Identical BSTs without building the trees. GFG Article

  16. **** Add all greater values to every node in a given BST /  Convert a BST to a Binary Tree such that sum of all greater keys is added to every key
    Algo: Since at each node we need all sum of all values greater than that node, we need to do reverse inorder traversal. 


  17. *** Remove BST keys outside the given range. GFG. Code
    Algo: Post order traversal. Start deleting node from the bottom as we move upwards in the tree.


  18. *** Check if all internal nodes of BST have only one child without building tree. GFG. Article  Code.
    Algo: 
    If a node – ‘currentNode’ in BST has only one child then that means all the nodes in BST are either in the left sub-tree of that node or in the right sub-tree. This further implies that all nodes would have values either greater than currentNode or all nodes would have values less than currentNode. Therefore in preorder traversal array all elements appearing after the currentNode would all be either greater than currentNode or less than currentNode. If this condition holds true for all elements of preorder array(except the last element: since that would be element for leaf node) then we can say that all internal nodes of BST have only one child.

  19. *** Find if there is a triplet in a Balanced BST that adds to zero  
    1. Convert to inorder and use the three sum logic. O(n^2).2. Convert to DDL. Then use the three sum logic.
    Time Complexity: Time taken to convert BST to DLL is O(n) and time taken to find triplet in DLL is O(n^2).
    Auxiliary Space: The auxiliary space is needed only for function call stack in recursive function convertBSTtoDLL(). Since given tree is balanced (height is O(Logn)), the number of functions in call stack will never be more than O(Logn).

    Similar: Find a pair with given sum in a Balanced BST


  20. **** Two BST are given. Print the inorder traversal of the merging of these two BST. GFG   C Code
    Algo: Convert both the BST into DDL. Both will be sorted. Now start printing the element from both in sorted order.


  21. ***** Merge Two Balanced Binary Search Trees – Write a function that merges the two given balanced BSTs into a balanced binary search tree GFG
    Algo:
    1. Insert elements of first tree to second – Take all elements of first BST one by one, and insert them into the second BST. Inserting an element to a self balancing BST takes Logn time (See this) where n is size of the BST. So time complexity of this method is Log(n) + Log(n+1) … Log(m+n-1). The value of this expression will be between mLogn and mLog(m+n-1). As an optimization, we can pick the smaller tree as first tree.
    2 Merge Inorder Traversals1) Do inorder traversal of first tree and store the traversal in one temp array arr1[]. This step takes O(m) time.
    2) Do inorder traversal of second tree and store the traversal in another temp array arr2[]. This step takes O(n) time.
    3) The arrays created in step 1 and 2 are sorted arrays. Merge the two sorted arrays into one array of size m + n. This step takes O(m+n) time(use merge sort).
    4) Construct a balanced tree from the merged array using the technique discussed in this post(Q 13 on this page). This step takes O(m+n) time.
    Time complexity of this method is O(m+n) which is better than method 1. This method takes O(m+n) time even if the input BSTs are not balanced.
    3. In-Place Merge using DLL
    We can use a Doubly Linked List to merge trees in place. Following are the steps.
    1) Convert the two given Binary Search Trees into doubly linked list in place
    2) Merge the two sorted Linked Lists (Refer this post for this step).
    3) Build a Balanced Binary Search Tree from the merged list created in step 2. (Refer this post for this step)
    Time complexity of this method is also O(m+n) and this method does conversion in place.


  22. ***** Two of the nodes of a Binary Search Tree (BST) are swapped. Fix (or correct) the BST. GFG
     Algo: Check GFG for edge cases(when node to be swapped are adjacent). See the code. How to set the prev node (in inorder traversal the prev is set after the left is already traversed and right is called).


  23.  **** BST from PreOrderGFG
    1. Code 1 (O(n)) – The first element of preorder traversal is always root. The next element will be either in the same level as the node created ( in the opposite subtree) or be a child of the node created.  Now that we know the root value, we make call to both the subtree with the min and max value of both these subtree. Check code and uncomment the debug part for clearer explanation.
    2. Code 2 (O(n^2)) – The first element of preorder traversal is always root. We first construct the root. Then we find the index of first element which is greater than root. This is the main cause of high time complexity. Let the index be ‘i’. The values between root and ‘i’ will be part of left subtree, and the values between ‘i+1’ and ‘n-1’ will be part of right subtree. Divide given pre[] at index “i” and recur for left and right sub-trees.
    3. This can be done using stack in O(n). GFG
  24. **** Sorted Linked List to Balanced BST. 
    Algo:
    1.
    Time complexity: O(nLogn)
    1) Get the Middle of the linked list and make it root.
    2) Recursively do same for left half and right half.
    a) Get the middle of left half and make it left child of the root created in step 1.
    b) Get the middle of right half and make it right child of the root created in step 1.
    Time complexity: O(nLogn) where n is the number of nodes in Linked List. After every middle element and you task is divided into two sub part. one in left part of middle and other one in right part and for making middle element as root you have to travese list every time till n/2 or n/4 whatever time which mean you can write time complexity as
    T(n) = 2T(n/2) + O(n)
    and as per master theorem time complexcity will be O(nlogn)
    2.
  25. [Pending] In-place conversion of Sorted DLL to Balanced BST

  26. **** Total number of possible Binary Search Trees with n keys. Code. Youtube. GFG. This is based on a concept Catalan Number

  27. Transform a BST to greater sum tree. GFG
    Time complexity of this method is O(n) as it does a simple traversal of tree.
    Similar: Convert a BST to a Binary Tree such that sum of all greater keys is added to every key and Add all greater values to every node in a given BST
    Algo: It’s reverse inorder traversal. Time complexity: O(n).
    We implemented this logic.


  28. Handle duplicates in Binary Search Tree. We can modify the basic BST structure to hold the count of duplicate.
    1) Height of tree is small irrespective of number of duplicates. Note that most of the BST operations (search, insert and delete) have time complexity as O(h) where h is height of BST. So if we are able to keep the height small, we get advantage of less number of key comparisons.
    2) Search, Insert and Delete become easier to do. We can use same insert, search and delete algorithms with small modifications (see below code).
    3) This approach is suited for self-balancing BSTs (AVL TreeRed-Black Tree, etc) also. These trees involve rotations, and a rotation may violate BST property of simple solution as a same key can be in either left side or right side after rotation.


  29. *** Print Common Nodes in Two Binary Search Trees – Use the logic of iterative inorder traversal. GFG
  30. [Pending] Construct all possible BSTs for keys 1 to N
  31. *** Count BST subtrees that lie in given range. GFG
  32. *** Count BST nodes that lie in a given range. GFG
    1. 
    Easy solution is O(n) by checking each element.
    2.
    If an element lies within the range then  that node lies within the range and it’s a possibility that both the left and right subtree also has element in that range. If the node does not lies in the range then we need to check the left or right subtree, by comparing the lower value of range. If current node is smaller than low value of range, then recur for right child, else recur for left child.Time complexity of the above program is O(h + k) where h is height of BST and k is number of nodes in given range.


  33.  How to implement decrease key or change key in Binary Search Tree. GFG
    Algo: The idea is to call delete for old key value, then call insert for new key value.  Time complexity of above changeKey() is O(h) where h is height of BST.


  34. Convert the given binary tree to binary search tree(BST) without changing the spatial structure of given binary tree. Article
    Algo:
    1. Create and inorder traversal array of binary tree and sort it.
    2. Now start the inorder tarversal of the given BT and start substituting values from array to the BST.
    In the above algorithm, Step #1 take O(n) + O(nlogn) time and step 2 takes O(n).  Therefore, overall time complexity of this method is O(nlogn)
Advertisements

Leave a Reply

Please log in using one of these methods to post your comment:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s