BST – Set 1

BST Visualizer  BST Complexity
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. Conversely 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. Link

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.

Insert
   – Complexity to insert an item is O(log n). So if we create a BST with n nodes, then overall it’s n(O(log n)).  If you are extremely unlucky (skewed tree), the complexity of insert is O(n) and thus it deteriorates to O(n^2) to construct a BST.
– 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.SO

Search – O(h) which is same as O(log(n)). Since a BST with n nodes has a minimum of O(log n) levels, it takes at least O(log n) comparisons to find a particular node. A BST can degenerate to a linked list(skewed tree), reducing the search time to O(n).

Delete  – O(log n)

In this worst-case scenario(consider a skewed tree): access, search, insertion and deletion is O(n).


  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 in-order traversal by sorting the only given traversal.


  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 larger 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.
    We find the next larger value in the right of this node. That will be in inorder successor. That value will lie in the left part of this right half. Once found replace the current node value and delete the other node whose value was substituted. We can use the same delete method to delete this as well.
    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.
    Time Complexity: O(n) Worst case happens for left skewed trees.


  5. *** Inorder predecessor and successor for a given key in BST. GFG. Code
    Algo:   We are arrived at the required node.
    If the left subtree of that node is not null, the predecessor will be the rightmost item in the left subtree.
    If the right subtree of that node is not null, the successor will be the leftmost item in the right subtree.
    Now we need to handle the case that if the left or right subtree is actually null. We take care of this when we recur for the left or right node.
    If  node.value <  key, we goto right sub-tree and the node where we diverted is our predecessor.
    If  node.value >  key, we goto left sub-tree and the node where we diverted is our successor.
    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  Check GFG Java Code.
    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. Check GFG 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.
    So we start with i = 0 (root node), now we want to reach the left most node using this array. So if we recur for the left child, at (2*i+1) until the array is over. we print this child. Now we recur for the right child. Complexity: O(n)
    – 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). GFG
    1.Do a inorder traversal and have a counter till k.  Code Time complexity: O(n).
    2. There’s an O(h) solution for the same. This requires changing the tree structure, each node will hold the metadata as to how number of nodes in left subtree. SO
    Similar: Largest and Second largest- Code Recursive Code Iterative


  11. *** Find k-th largest element in BST GFG or Second largest element in BST
    Algo: Do a reverse inorder traversal. We move to the rightmost recursively and start moving up the tree.
    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).


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

  13. Print BST keys in the given range in sorted order. GFG
    Algo: We can do a simple inorder traversal and print all values that fall in the given range. We can make intelligent choice of not recurring to all the left and right node by applying a check before recursively calling left and right based on k1 and k2 ( k1<k2).


  14. **** 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.
    If we are given a sorted array, we can use this logic to build the tree in O(n)
    Read this


  15. **** Largest BST in BT. Youtube . Code GFG
    Algo:
    There are two ways. Either we start from the top and keep checking if a BST can be formed using that node as the root. If not we move to left and right and keep checking. This takes O(n^2) times.
    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.


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

  17. **** 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. 


  18. *** 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. Since it’s a BST we can use it’s fundamental property of how the nodes are arranged.


  19. *** Check if all internal nodes of BST have only one child without building tree. GFG. Article  Code.
    Algo:
    1. 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.
    Basically all the descendants of a node must either be larger or smaller than the node. This has O(n^2) complexity.

  20. *** 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). O(n) extra space
    2. Convert to DDL in-place  and 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).
    Code to convert BT to DDL in-place

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


  21. **** Two BST are given. Print the in-order 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.


  22. ***** 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 Traversals
    1) 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 logic).
    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.
    Basically if we have twi BST just convert them into DDL and merge them.


  23. ***** Two of the nodes of a Binary Search Tree (BST) are swapped. Fix (or correct) the BST. GFG
     Algo:
    – Generate the in-order traversal and then find the out of order element. Handle the edge cases when swapping.
    – We can generate the in-order traversal of the BST and store the node in an array instead of only storing the value. Now we can find the element out of order in a sorted array – start from beginning and start from end and get the out of order nodes. Now swap the data of these nodes


  24.  **** 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 index 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


  25. **** Sorted Linked List to Balanced BST. GFG
    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 traverse 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)


  26. [Pending] In-place conversion of Sorted DLL to Balanced BST

  27. **** Total number of possible Binary Search Trees with n keys. Code. Youtube. GFG. This is based on a concept Catalan Number
    Algo: Try to pick a set of number and form a tree. Like start with 1,2,3…numbers and see how many BST can be formed. Try to generalize that.
    Like suppose we have 3 number, 10, 11 and 12. So if 10 is root how many BSTs can be formed, next what if 11 is root and so on. So if 10 is root, then there will be 0 items in BST of left side and 2 numbers on BST of right side. Now we know how many BST can be formed when there’s one item on left and two item on right. Next if 11 is root, then there will be 1 item on both side of root. So we are using the previously calculated result here.
    So it will be t[3] = t[0]*t[2] + t[1]*t[1] + t[2]*t[0] when we keep 10 , 11 and 12 as root respectively. Write this as code with base case as t[0] = t[1] = 1


  28. 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.


  29. 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.


  30. *** Print Common Nodes in Two Binary Search Trees.  GFG.
    1. Get in-order traversal of both BST and compare. Time complexity of this method is O(m+n) where m and n are number of nodes in first and second tree respectively. This solution requires O(m+n) extra space.
    2. Use the logic of iterative in-order traversal. Not easy.


  31. [Pending] Construct all possible BSTs for keys 1 to N

  32. *** Count BST subtrees that lie in given range. GFG  –
    Algo: This is different from the question where we need to find the number of nodes in a given range.
    We need to verify each subtree and also check if each value lies in the given range. So we will have to pass the min and max value to each node (something similar like when we need to validate of a BT is a BST).


  33. *** 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.


  34. ** 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.


  35. Convert the given binary tree to binary search tree(BST) without changing the spatial structure of given binary tree. Article
    Algo:
    1. Create an inorder traversal array of binary tree and sort it.
    2. Now again traverses given binary tree in inorder fashion and simultaneously it traverses sorted inorder array. At each node visit of binary tree, the value of that node is changed to corresponding element in the inorder array. That is value of first node visited during inorder traversal is changed to value of element at 0th index in sorted inorder array, value of second node visited during inorder traversal is changed to value of element at 1st index and so on
    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 )

Google+ photo

You are commenting using your Google+ 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 )

w

Connecting to %s