https://www.youtube.com/watch?v=pYT9F8_LFTM&t=939s

Binary Search Tree (BST)

BST -->

-- a Binary Tree

-- all the nodes of the left subtree have to smaller or equal than the nodes of the right subtree.

Consider the tree above:

We can see that 10, 8, 12 are smaller that 15 and 20, 17, 25 are greater than 15. So we are good at this level.

Then, we can see that 8 is smaller than 10 and 12 is greater than 10. So we are good at this level too.

Similarly, we can see that 17 is smaller than 20 and 25 greater than 20. So again, we are good at this level too.

Hence the above tree is a proper BST.

Now suppose we changed 12 to 16. Now is this a BST?

For node 10, it is as 8 is smaller and at its left and 16 is greater and at its right.

But for the root node 15, 16 is greater but its at its left. So its not a BST anymore.

Search in BST: Like Binary search only. n --> n/2 --> n/4 ...... --> 1 search space goes on reducing. So its's O(log n)

Balanced and unbalanced tree: Balanced tree means the difference between the heights of the left subtree and right subtrees is less than or equal to one.

Search in BST best case is O(log n) for balanced BST and worst case is O(n) (for unbalanced BST).

Insert in BST - average case : O(log n) for balanced BST

Delete in BST - average case : O(log n)

Inorder Traversal of BST: First visit the left subtree, then the root node and then the right subtree. Time complexity is O(n).

Algo for inorder traversal:

Start from root node, if there is a left child, go to that, keep going till the leaf left child, once there, visit that node. Now since its a leaf child, it wont have a right child, so go up, now at every node check if it has a right child too, and visit them. if at a node you are coming in from the left then that node isnt visited else if you are coming at it from right then its already visited.

The o/p of the inorder traversal of a BST is in sorted order.

inorder traversal

postorder traversal

preorder traversal

with recursive code

find min max in BST

https://www.youtube.com/watch?v=wcIRPqTR3Kc

-- for insert and delete node from BST

https://www.youtube.com/watch?v=FvdPo8PBQtc

-- to construct a BST from a given array

Insert in BST

Search in BST

Delete from BST -- Has three cases:

1. Removing a leaf node. DOesnt affect the tree structure.
2. Removing a node with one child: Simply remove that node and point its parent to that node's child.
3. Removing a node with two children: So what we do is we find the node in the tree which is the next biggest than the current removal node. To find the next biggest: go to that node's right subtree and in that right subtree go to its far left node. Replace the current node with this new far most left node.

OR

for case 3: you can go for max in left subtree instead of min in right subtree.

Inorder successor in BST

Binary Tree Traversal:

Breadth first search

1. Level Order

Depth first search

1. Preorder

2. Postorder

3. Inorder

In Breadth first search traversal:

Level Order:

Ypu go from top to bottom and left to right:

Level Order traversal: D B F A C E G

In Depth first search traversals:

https://www.youtube.com/watch?v=gm8DUJJhmY4

if we start in one direction, then we first visit the complete subtree in that direction and only then we change our direction.

So we can have three ways:

Preorder traversal

<root> <left subtree> <right subtree>

Inorder traversal

<left subtree> <root> <right subtree>

Post order traversal

<left subtree> <right subtree> <root>

Inorder: A B C D E F G

Preorder: D B A C F E G

Postorder: A C B E G F D

Tricks for traversals: https://www.youtube.com/watch?v=eL8NZ-21lqI

How to construct trees: https://www.youtube.com/watch?v=0QOtVxTVj4w

https://www.youtube.com/watch?v=cGlNehp57Y0

Find Inorder Successor in a BST:

Inorder successor means the node that comes immediately after the given node in its inorder traversal.

https://www.youtube.com/watch?v=5cPbNCrdotA&index=37&list=PL2_aWCzGMAwI3W_JlcBbtYTwiQSsOTa6P

case 1: Node has right subtree

Go deep to leftmost node in right subtree OR find min in right subtree.

case 2: No right subtree

Go to the nearest ancestor for which the given node would be in left subtree.

Find Inorder Predecessor in a BST:

https://www.youtube.com/watch?v=yO0niFJhSf8

case 1: Node has left subtree

predecessor is max value in left subtree

case 2: Node has no left subtree

Go to the nearest ancestor for which the given node would be in right subtree.

If you cannot go further then that node is the smallest element.

Find min and max in a BST:

Min is the leftmost node and max is the rightmost node.

Height of a tree:

Number of edges in longest path from root to leaf node.

Height of a node: Number of edges in longest path from that node to leaf node.

Depth of a node: Number of edgees in longest path from root to that node.