Binary Search Tree | Sqrt

Phone: - Questions from LC tagged LinkedIn.
- Get sqrt(x). Output a floored integer if result is not a perfect square. sqrt(18) = 4
- Implement BST, insert, delete, search.
- Design a dashboard for service logs stats (sort and aggregate). Scale from 1 to more machines. Discuss async and realtime as different scenarios.

class BinarySearchTree {
    /* Class containing left and right child of current node and key value*/
    class Node {
        int key;
        Node left, right;
        public Node(int item) {
            key = item;
            left = right = null;
    // Root of BST
    Node root;
    // Constructor
    BinarySearchTree() { 
        root = null; 
    // This method mainly calls insertRec()
    void insert(int key) {
       root = insertRec(root, key);
    /* A recursive function to insert a new key in BST */
    Node insertRec(Node root, int key) {
        /* If the tree is empty, return a new node */
        if (root == null) {
            root = new Node(key);
            return root;
        /* Otherwise, recur down the tree */
        if (key < root.key)
            root.left = insertRec(root.left, key);
        else if (key > root.key)
            root.right = insertRec(root.right, key);
        /* return the (unchanged) node pointer */
        return root;
    // This method mainly calls InorderRec()
    void inorder()  {
    // A utility function to do inorder traversal of BST
    void inorderRec(Node root) {
        if (root != null) {

   // This method mainly calls deleteRec()
    void deleteKey(int key)
        root = deleteRec(root, key);
    /* A recursive function to insert a new key in BST */
    Node deleteRec(Node root, int key)
        /* Base Case: If the tree is empty */
        if (root == null)  return root;
        /* Otherwise, recur down the tree */
        if (key < root.key)
            root.left = deleteRec(root.left, key);
        else if (key > root.key)
            root.right = deleteRec(root.right, key);
        // if key is same as root's key, then This is the node
        // to be deleted
            // node with only one child or no child
            if (root.left == null)
                return root.right;
            else if (root.right == null)
                return root.left;
            // node with two children: Get the inorder successor (smallest
            // in the right subtree)
            root.key = minValue(root.right);
            // Delete the inorder successor
            root.right = deleteRec(root.right, root.key);
        return root;

Get one-to-one training from Google Facebook engineers

Top-notch Professionals

Learn from Facebook and Google senior engineers interviewed 100+ candidates.
Most recent interview questions and system design topics gathered from aonecode alumnus.
One-to-one online classes. Get feedbacks from real interviewers.

Customized Private Class

Already a coding expert? - Advance straight to hard interview topics of your interest.
New to the ground? - Develop basic coding skills with your own designated mentor.
Days before interview? - Focus on most important problems in target company question bank.