Satraj Shanibook is good.
binary search tree is subset ofbinary_tree.
- Every key has to be distinct, no duplicate.
- All left keys should be smaller than the node and all right keys should be greater than the node.
- Binary search tree is used to create sets and sortedsets, that is why duplicates are not allowed. You can use a corresponding map if you need to manage duplicate values.
Empty tree is representated as: - None in python - null in js
binary_tree operations:
- tree traversal,inorder_traversal ,preorder_traversal,postorder_traversal,level_order_traversal
- Max/ min in binary tree
- Size of binary tree
- Height of binary tree.
It is not just to store data but can practically be used to store data very efficiently in your applications.
Operations ofbinary_search_tree
self_balancing_BST , implemented by set incpp andtreeset in Java,orderset inpython,set injavascript . Problem: User is giving input in random order but you want to store them in sorted order.
-
If you use array theinsertion,deletion and other operations will take linear time, O(n)
-
Another application isHeap , heaps are powerful to get max and min in O(1) time using respectivemin_heap andmax_heap.
-
Both are complex so nobody will ask to implement them.
-
Both should not let the tree height go more thanlog_n
-
restructuring_of_tree on insertion, deletion.
-
AVL_Tree is very strict, height has to be very accurate, sorestructuring_of_tree will be required at every operation.
-
hash andself_balancing_BST are good competitors for some problems, if you have operation like max, min then go for .
-
set vs map: set stores only keys but map stores both key and value.
-
lis solution is very interesting and complex and in DP you can’t come directly to solutions, you mostly need to know as there is a lot of mathematics behind it.
-
ifoverlapping_subproblems then it isgreedy_approach. Recursion with tree will comes with attempting more problems, it may be difficult to wrap around initially.
which one of AVL and Red Black Tree is used more practically
Q. DSA to prepare formachine_learning jobs? Ans. Go through latest interview experience.