Binary Search Trees, Balance Search Trees, 2-3 ST, Red- Black BST

ALSO CHECK: Algorithms and System Design Interview Questions

Tree Data Structure

• If we compare sorted arrays with linked list: Search is fast in SA (O(logn)) and slow in LL (O(n)), but insert & delete is slow in SA (O(n)) and fast in LL (O(1)).
• Binary search trees are very balanced in the sense that all these common operations like insert, delete, and search take about the same time (log n).
• In Binary search trees we have the nodes, which contain the data. Nodes are connected to other nodes through edges. The top node of the tree is called the root node (in a tree data structure, there can only be one root node).
• A node which has no children is called a leaf node. 
• Any node may be considered to be the root of a subtree, which consists of its children and its children's children and so on. The level of a node tells us how far it is from the root. 

Binary Tree

• In a binary tree every node can have, at most, two children. 
• A node may have no children, which makes them a leaf node, but cannot have more than 2 children.
• The left and right nodes, connected to a particular nodes are known as left child and right child. 

Binary Search Tree

• A binary search tree is a binary tree.
• All the children to the left, which means it's immediate left child and then the grandchildren and so on, have a data value less than that of the parent node itself. 
• All the children to the right of the node have data values greater than that of the node. 
• This property in a binary tree makes it quite fast to search items.

How to search an item in a binary search tree?

• We always start from the root, because the tree has a reference to the root node only.
• If you find the data in the tree, we will just return the node object itself, else we'll return a null. 
• When searching for an item in a binary search tree, we start at the root, compare the item to be searched with the root. If it's equal, we return it; if not, we check if it is larger or smaller. If it is smaller, we search the left sub-tree; if greater we will search in right sub-tree, we might need to do that recursively.

How to insert a new node in a Binary Tree?

• While inserting a new node, we need to keep looking for a place where to insert this new node such that the binary search tree property is not violated. Which means the right child should be greater than or equal to the current node, and the left child should be less than the current node. 
• We can do the equality thing for the right child in case duplicate values are allowed. So, if the data is equal to the current node, we insert the new value as a right child. But that may not be the immediate right child.
• We do the insertion recursively, we start at the root and compare the two values. If the new item is greater than root node, we need to insert it somewhere in the right subtree, else we will insert it in left subtree.

ALSO CHECK: Level Order Traversal of a Binary Tree

How to delete a node from a Binary Tree?
While deleting the node, we need to consider three cases:
1). When the node to be deleted is a leaf. That is it has no children.
2). When the node to be deleted has one child.
3). When the node to be deleted has two children.

Case 1:
When we want to delete a leaf node, we just need to find the node which need to be deleted, and then find the parent. If the node to be deleted is the left child, we will set the reference of left child in its parent node as null, we need to do the same if its the right child.

Case 2:
When the node to be deleted has one child. First we need to find the node to be deleted (lets say C), now we need to find its parent (lets say P) and the only child (either left or right, lets say GC). We just need to set GC as the child of P.

Case 3:
Deletion becomes complicated when the node to be deleted has two children. Lets take an example, suppose we need to delete node 33 from the below tree:

After deleting 33, which node should take its place? It should be the node having data that is just greater than the data in the node to be deleted (33), but less than the right child of the current node (39). To do this, we go to the right child of the node to be deleted and keep going to the left child until there is no left child (because all nodes in the right subtree has numbers larger than the current node).

After iterating we will find a node, which has no left child. This node will be called as successor of current node (which is to be deleted). Then we need to bring the successor to the place of the current node. Now the left child of the current node should become the left child of the successor and the right child of the current node (that's the node to be deleted) should become the right child of the successor node.

What if the successor has a a right child? In that case after bringing the successor to the place of the node to be deleted,  the right child of the successor should become the left child of the parent of the successor.

How can we find the maximum and minimum values from a a Binary search tree?

• To find the smallest value, we need to start from the root and keep going to the left child until we reach a node which does not have a left child.
• To find the largest value, start from the root and keep going to the right child until we come to a note which does not have a right child (this node may have a left child)

1). TreeNode class


2). BinarySearchTree class

Tree Traversal
The three most common ways to traverse a binary tree are these: in-order, pre order, and post order.

• In Order for the above tree: 12 25 27 33 34 39 48 52 60 65 72 78 90
• Pre Order: 52 33 25 12 27 39 34 48 65 60 78 72 90
• Post Order: 12 27 25 34 48 39 33 60 72 90 78 65 52

In-order traversal: we first traverse the left sub tree, and this is done recursively. First we traverse the left sub tree, then we go to the root of the tree, and finally we traverse the right sub tree recursively.

1). Add below methods in TreeNode class
public void traverseInOrder() {
    if (this.leftChild != null)
       this.leftChild.traverseInOrder();
    System.out.print(this + " ");
    if (this.rightChild != null)
       this.rightChild.traverseInOrder();
}
2). Implement below method in BinarySearchTree Class
public void traverseInOrder() {
     if (this.root != null)
        this.root.traverseInOrder();
     System.out.println();
}
Pre-order traverse: We first visit the root node, then we traverse the left sub tree, recursively, in the pre-order way. And then the right sub tree is traversed recursively, the pre-order way.

Post-Order Traversal: In this case, traverse the left sub tree first, then the right sub tree, and finally, visit the root mode.

Balance Search Trees

• Ideally, we should keep our binary search trees perfectly balanced. In an N-node tree, we would like the height to be ~lg N so that we can guarantee that all searches can be completed in ~lg N compares, just as for binary search. But maintaining perfect balance for dynamic insertions is too expensive.

How to check if a given Binary Tree is BST or not?

If inorder traversal of a binary tree is sorted, then the binary tree is BST. The idea is to simply do inorder traversal and while traversing keep track of previous key value. If current key value is greater, then continue, else return false. 

What is an AVL tree?

An AVL (Adelson, Velskii, and Landi) tree is a height balancing binary search tree in which the difference of heights of the left and right subtrees of any node is less than or equal to one. This controls the height of the binary search tree by not letting it get skewed. This is used when working with a large data set, with continual pruning through insertion and deletion of data.

2-3 Search Trees

• This tree allowed 1 or 2 keys per node.
• 2-node: one key and two children.
• 3-node: two keys, three children.
• 2-3 trees have perfect balance, i.e every path from root to null link has same length.

In the above 2-3 search tree, the root node contain 2 keys that's 37 and 50.The left node contains 2 keys, 30 and 35 and has 3 children. The left children will have keys less than 30, right will have keys greater than 35 and the middle one will have keys between 30 and 35.

Insertion in 2-3 trees

(1). Let's say we have a 2-3 tree.
(2). In the step 2 we will insert K in the 2-3 tree. Since its less than root node (thats M), so we will go left. Now since K is greater than both E and J, so we will got to the right child of EJ, which is L. Now since K is less than L, we will add it before L,now the node will have two keys K and L, and their 2 children will be replaced with 3.
(3).Let's insert Z now. Since Z is greater than M, we will go to the right child (thats R), since Z is greater than R, we will again go to the right child of R (which is SX). Now Z is greater than X, but the X does not have any right child, so our search ends here. Temporary we will add Z with S and X.
(4). Since a node can contain only 2 keys, we will split SXY and pass the middle key to their parent (which is R). Now since the node which had contained R, now has 2 keys (R and X), so it must contain 3 children.

Lets take another example to understand double split while inserting in 2-3 Search Tree:

(1). Lets say we have a tree in which root node contains E and R.
(2). Now lets say we want to insert L in the tree, since L comes between E and R, we will insert it in the middle child. The middle child of ER contains H and P. lets temporary insert L with them.
(3). Since any node in a 2-3 can contain either one or two keys, we need to split the node with keys HLP. We will move L to the parent, now the parent will contain ELP.
(4). Again we need to split the parent node. Since the node containing ELP does not have any parent, we need to create a new parent which has the value L, by doing this the height of the tree will increase by 1.

Example to construct a 2-3 tree from scratch

Red Black Binary Search Tree
Red black tree is a self balanced binary search tree, also known as symmetric binary B tree.

Properties of a red black tree:

• In Red black tree, no data is stored at the leaves.
• A node is either red or black.
• The root and leaves (NIL) are black.
• If a particular node is red, then its children are black.
• All paths from a node to its NIL descendent's contain the same number of black nodes.
• Black height of the red black tree is the number of black nodes from root to the NIL nodes. Each node has its own black height.
• In case of red black tree each node requires one storage bit to keep a track of color.
• The longest path (root to the farthest NIL) is no more than twice the length of the shortest path (root to the nearest NIL). The shortest path means all black nodes, while the in longest path all the alternate red an black nodes are counted.
• Time complexity for search, insert and remove in a red-black tree is O(log n). Space complexity is O(n), where n is the number of nodes in the tree.
• Read-only operations such as traversing and searching in Red Black Tree are similar to Binary search tree. But, insertion and deletion operations require the modifications in the tree structure and we may need to rearrange the tree.

Why we need Red-Black Trees?

• Most of the BST operations (e.g. search, max, min, insert, delete  take O(h) time, where h is the height of the Binary search tree. The cost of these operations may become O(n) for a skewed Binary tree. 
• If we make sure that height of the tree remains O(Logn) after every insertion and deletion, we can guarantee an upper bound of O(Logn) for all these operations. 
• The height of a Red-Black tree is always O(Logn), where n is the number of nodes in the tree.

What is the black height of a Red-Black Tree?

• Black height is number of black nodes on a path from root to a leaf. 
• Leaf nodes are also counted black nodes. 
• A Red-Black Tree of height h has black-height >= h/2.

Left Rotation in Red-Black BST : We orient a right leaning red link to lean left.

Java Code for left rotation in Red-Black BST:
public TreeNode rotateLeft(TreeNode h)
{
     TreeNode x=h.getRightChild();
     h.setRightChild(x.getLeftChild());
     x.setLeftChild(h);

     x.setColor(h.getColor());
     h.setColor("RED");
     return h;
}

Right Rotation in Red-Black BST : We orient a left leaning red link to lean right.

Java Code for right rotation in Red-Black BST:
public TreeNode rotateRight(TreeNode h)
{
     TreeNode x=h.getLeftChild();
     h.setLeftChild(x.getRightChild());
     x.setRightChild(h);

     x.setColor(h.getColor());
     h.setColor("RED");
     return h;
}

Color Flip in Red-Black BST

Java Code for color flip in Red-Black BST:
public void flipColor(TreeNode h)
{
     h.setColor("RED");
     h.getLeftChild().setColor("BLACK");
h.getRightChild().setColor("BLACK");
}

How can we find the minimum depth of a Binary Tree?
The minimum depth is the number of nodes along the shortest path from the root node down to the nearest leaf node.
Time complexity of below solution is O(n) as it traverses the tree only once.
public int minimumDepth(TreeNode root) 
{ 
     // Corner case. Should never be hit unless the code is 
     // called on root = NULL 
     if (root == null) 
          return 0; 
  
     // Base case : Leaf Node. This accounts for height = 1. 
     if (root.getLeftChild() == null && root.getRightChild() == null) 
          return 1; 
  
     // If left subtree is NULL, recur for right subtree 
     if (root.getLeftChild() == null) 
          return minimumDepth(root.getRightChild()) + 1; 
  
     // If right subtree is NULL, recur for left subtree 
     if (root.getRightChild() == null) 
          return minimumDepth(root.getLeftChild()) + 1; 
  
     return Math.min(minimumDepth(root.getLeftChild()), minimumDepth(root.getRightChild())) + 1; 
} 

The above method may end up with complete traversal of Binary Tree even when the topmost leaf is close to root. A better way to do this is to do Level Order Traversal. In this while doing traversal, we return depth of the first encountered leaf node.
// A queue item (Stores pointer to
// node and an integer)
static class qItem {
     TreeNode node;
     int depth;

     public qItem(TreeNode node, int depth) {
          this.node = node;
          this.depth = depth;
     }
}

static int minDepth(TreeNode root)  
{  
     // Corner Case  
     if (root == null)  
          return 0;  
  
     // Create an empty queue for level order traversal  
     Queue < qItem >  q = new LinkedList <  > ();  
  
     // Enqueue Root and initialize depth as 1  
     qItem qi = new qItem(root, 1);  
     q.add(qi);  
  
     // Do level order traversal  
     while (q.isEmpty() == false)  
     {  
          // Remove the front queue item  
          qi = q.peek();  
          q.remove();  
  
          // Get details of the remove item  
          TreeNode node = qi.node;  
          int depth = qi.depth;  
  
          // If this is the first leaf node seen so far  
          // Then return its depth as answer  
          if (node.getLeftChild() == null && node.getRightChild() == null)  
               return depth;  
  
          // If left subtree is not null, add it to queue  
          if (node.getLeftChild() != null)  
          {  
               qi.node = node.getLeftChild();  
               qi.depth = depth + 1;  
               q.add(qi);  
          }    
          // If right subtree is not null,  add it to queue  
          if (node.getRightChild() != null)  
          {  
               qi.node = node.getRightChild();  
               qi.depth = depth + 1;  
               q.add(qi);  
          }  
     }  
     return 0;  
}  

How can we find the maximum path sum in a Binary Tree?
For each node there can be four ways that the max path goes through the node:
1. Node only
2. Max path through Left Child + Node
3. Max path through Right Child + Node
4. Max path through Left Child + Node + Max path through Right Child

We need to keep trace of four paths and pick up the max one in the end. The root of every subtree need to return maximum path sum such that at most one child of root is involved. This is needed for parent function call.
//An object of Res is passed around so that the 
//same value can be used by multiple recursive calls. 
class Res { 
public int val; 
} 

public class MaxPathBST {
TreeNode root; 

// This function returns overall maximum path sum in 'res' 
// And returns max path sum going through root. 
int findMaxUtil(TreeNode node, Res res) 
{ 
// Base Case 
if (node == null) 
return 0; 

// l and r store maximum path sum going through left and 
// right child of root respectively 
int l = findMaxUtil(node.getLeftChild(), res); 
int r = findMaxUtil(node.getRightChild(), res); 

// Max path for parent call of root. This path must 
// include at-most one child of root 
int max_single = Math.max(Math.max(l, r) + node.getData(), node.getData()); 

// Max Top represents the sum when the Node under 
// consideration is the root of the maxsum path and no 
// ancestors of root are there in max sum path 
int max_top = Math.max(max_single, l + r + node.getData()); 

// Store the Maximum Result. 
res.val = Math.max(res.val, max_top); 

return max_single; 
} 

int findMaxSum() { 
return findMaxSum(root); 
} 

// Returns maximum path sum in tree with given root 
int findMaxSum(TreeNode node) { 
Res res = new Res(); 
res.val = Integer.MIN_VALUE; 
findMaxUtil(node, res); 
return res.val; 
} 

/* Driver program to test above functions */
public static void main(String args[]) { 
MaxPathBST tree = new MaxPathBST(); 
tree.root = new TreeNode(10); 
tree.root.leftChild = new TreeNode(2); 
tree.root.rightChild = new TreeNode(10); 
tree.root.leftChild.leftChild = new TreeNode(20); 
tree.root.leftChild.rightChild = new TreeNode(1); 
tree.root.rightChild.rightChild = new TreeNode(-25); 
tree.root.rightChild.rightChild.leftChild = new TreeNode(3); 
tree.root.rightChild.rightChild.rightChild = new TreeNode(4); 

System.out.println("maximum path sum is : " + tree.findMaxSum()); 
} 
}

-K Himaanshu Shuklaa..