A binary tree is a Binary Search tree if and only if:
- All values in left subtree of a node are less than value in node.
- All values in right subtree of a node are greater than value in node.
For eg.
1.Insert value in a binary search tree:
While inserting a new value in a binary search tree only left or right subtree is traversed from root by comparing value of root with new value.
If new value is less than root then add it to the left subtree of root else add to right subtree of root. This can be done easily using recursion.
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 |
public void Insert(Node root, int val) { Node newNode= new Node(null, null, val); if (root == null) { root = newNode; return; } Node tempNode= root; if (tempNode.value > val) { if(tempNode.left==null) { tempNode.left = newNode; return; } else { Insert(tempNode.left, val); } } else if (tempNode.value < val) { if(tempNode.right==null) { tempNode.right = newNode; return; } else { Insert(tempNode.right, val); } } } |
New node always inserted at the end of a existing tree, so while inserting number of nodes traversed depends on the height of a binary tree.
2. Delete a value from binary search tree:
When a value is less than root then left subtree of root is traversed and if present, deleted from tree. If value to be deleted is greater than root, then right subtree of root is traversed and if present value is deleted.
If value to be deleted is present in tree then there are 3 possible scenarios:
1. Value present in a leaf node of a tree.
2. Node with that value has one child (either left or right).
3. Node with that value has both children.
If node to be deleted is a leaf node then we remove that node by assigning null value to the appropriate child pointer of its parent.
If that node has only one child then we replace that node with its existing child.
If node have both children, then we need to make sure that after deleting node, binary search tree properties are maintained. So to make sure that we can either select maximum value from left subtree of that node or select minimum value from right subtree of that node and replace it with node to be deleted.
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 |
public Node Delete(Node root, int val) { if (root == null) { return root; } if (root.value > val) root.left = Delete(root.left, val); if (root.value < val) root.right = Delete(root.right, val); if (root.value == val) { if (root.left == null && root.right == null) { root = null; return root; } else if (root.left == null) { root = root.right; } else if (root.right == null) { root = root.left; } else { Node min = TreeMinimum(root.right); root.value = min.value; root.right = Delete(root.right, min.value); } } return root; } public Node TreeMinimum(Node root) { if (root.left == null) return root; else TreeMinimum(root.left); return root; } |
If value to be deleted is present in a leaf node or in worst case it does not present in a tree, in both cases number of nodes traversed in this case depends on a height of a tree.
3. Validate if given binary tree is binary search tree or not:
If for all the nodes in a binary tree, binary search tree constraints(Value in node always greater than values in its left subtree and value in a node always less than values in its right subtree) are satisfied then that tree is a binary search tree.
Validating binary search tree can be done in a recursive way. For each root value, we are checking if that value is in between range[min,max]. For root of a tree min value is Int Min value and max value is Int Max value.
For a node in a left subtree of a node, minimum value is a Int Min value but maximum value is value present in its parent. As we know,values in left subtree of a node always less than value in node in binary search tree.
For a node in a right subtree of a node, minimum value is a value present in its parent and maximum value is Int max. As we know, values in right subtree of a node are always greater than value in node in binary search tree.
|
1 2 3 4 5 6 7 8 9 10 11 |
public bool CheckIfBST(Node rt, int min, int max) { if (rt == null) return true; if (rt.value > min && rt.value < max && CheckIfBST(rt.left, min, rt.value) && CheckIfBST(rt.right, rt.value, max)) { return true; } else return false; } |
While checking if tree is binary search tree or not, all nodes a tree are traversed so complexity is O(n).