CareerCup

Simple approach is:

insert element in tree:
whenever tree is unbalanced do left or right rotation: this is exactly AVL tree prob

Node *BalancedBST(int A[], int start, int end) {
if(start< end) {
int mid = (start + mid)/2;
Node *temp = (Node *) malloc(sizeof(Node));
temp->val = A[mid];
temp->left = BalancedBST(start, mid-1);
temp->right = BalancedBST(mid+1, end);
return temp;
}
else return NULL;
}

insert_node(node *root, int key)
{
if (key > root->key) {
if (has_one_child(root)) {
if (root->right) {
int temp=root->key
int temp1 = successor(root->key);
delete(successor(root->key));
root->key= temp1;
root->left=(node *)malloc(sizeof(node));
root->left->key=temp;
insert_node(root,key)
}
} else {
insert_node (root->right, key);
}
} else {
if (has_one_child(root)) {
if (root->left) {
int temp=root->key
int temp1 = predecessor(root->key);
delete(predecessor(root->key));
root->key= temp1;
root->right=(node *)malloc(sizeof(node));
root->right->key=temp;
insert_node(root,key)
} else {
insert_node(root->left, key);
}
}
}

int buildBinaryTree(node *current, int data) {
if (current == NULL ) {
current = newNode(data);
current->left = NULL;
current->right = NULL;
return 0;
}

if (current->data >= data) {
buildBinaryTree(current->left, data);
else if (current->data < data) {
builBinaryTree(current->right, data);
}
}

int main (){
node * temp = NULL;
for(int i =0; i< n; ++i) {
buildBinaryTree(temp,arry[i]);
}
return 0;
}

I think this is wht happens in Red Black Tree, Same concept of having balanced tree with property of BST.

The interviewer is asked for implementation of self-balance tree. Most self-balance tree implementation are complex and hard to remember. So far, left-lean red black tree[1] is the easiest and most memorable implementation I've ever seen.

ref1: Left-Leaning. Red-Black Trees. Robert Sedgewick. Princeton University.

case class Node(value: Int,
           isRed: Boolean = true,
           left: Option[Node] = None,
           right:Option[Node] = None) {


  def flipColors: Node = {
    this.copy(isRed = !this.isRed,
      left = left.map(l => l.copy(isRed = !l.isRed)),
      right = right.map(r => r.copy(isRed = !r.isRed))
    )
  }

  def rotateLeft: Node = {
    val left = this.copy(right = this.right.flatMap(_.left), isRed = true)
    val ret = this.right.get.copy(left = Some(left), isRed = this.isRed)
    return ret
  }

  def rotateRight: Node = {
    val right = this.copy(left = this.left.flatMap(_.right), isRed = true)
    val ret = this.left.get.copy(right = Some(right), isRed = this.isRed)
    return ret
  }
}

case class LLRB(root: Option[Node] = None) {

  def insert(value: Int): LLRB = {
    return new LLRB(Some(insert(root, value)))
  }

  private def insert(head: Option[Node], value: Int): Node = {
    head match {
      case None => new Node(value)
      case Some(v) => {
        var h = v
        if (isRed(h.left) && isRed(h.right)) {
          h = h.flipColors
        }

        if (h.value < value) {
          h = h.copy(right = Some(insert(h.right, value)))
        } else {
          h = h.copy(left = Some(insert(h.left, value)))
        }

        if (isRed(h.right)) {
          h = h.rotateLeft
        }
        if (isRed(h.left) && isRed(h.left.flatMap(_.left))) {
          h = h.rotateRight
        }
        h
      }
    }
  }

  private def isRed(node: Option[Node]): Boolean = {
    return node.map(_.isRed).getOrElse(false)
  }
}