BST (Binary Search Tree) is a binary tree in which
Left node and its children are smaller than the root.
Right node and its children are greater than the root.
No duplicate nodes.
InOrder traversal of BST produces sorted output which can be represented in an array.
We could 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.
Insertion – New key always inserted at leaf.
The lowest common ancestor (LCA) between two nodes n1 and n2 is defined as the lowest node in T that has both n1 and n2 as descendants (where we allow a node to be a descendant of itself).
Balanced BST or Self balancing BST or Height balanced BST – BST for which height (number of levels from root) is minimal.
Converting BST to a balanced BST – Inorder traversal of the given BST gives a sorted array. Pick the middle element of the array as root and construct the left of the middle in the array as left tree and right of middle as right tree. Repeat the above process for the left and right segments in the array.
Tips for solving problems on BST.
Use recursion or stack.
Prefer inorder traversal which gives a sorted array
At every node, check the lesser and greater condition.
If the current node is null, that represents that you are in leaf node.
Approach reducing the search space to improve the time complexity.
