📢 Too many exams? Don’t know which one suits you best? Book Your Free Expert 👉 call Now!

    Question

    Consider the following Java-like pseudo-code for

    inserting a node into a Binary Search Tree (BST):     ```java     class Node {         int data;         Node left, right;         public Node(int item) {             data = item;             left = right = null;         }     }     class BST {         Node root;         BST() {             root = null;         }         void insert(int data) {             root = insertRec(root, data);         }         Node insertRec(Node root, int data) {             if (root == null) {                 root = new Node(data);                 return root;             }             if (data < root.data) {                 root.left = insertRec(root.left, data);             } else if (data > root.data) {                 root.right = insertRec(root.right, data);             }             // If data == root.data, do nothing (assume no duplicates)             return root;         }     }     ```     If you insert the following sequence of numbers into an initially empty BST: `50, 30, 70, 20, 40, 60, 80`, what will be the data of the node that has `40` as its right child? 
    A 30 Correct Answer Incorrect Answer
    B 50 Correct Answer Incorrect Answer
    C 20 Correct Answer Incorrect Answer
    D 60 Correct Answer Incorrect Answer

    Solution

    Let's trace the BST construction:         1.  Insert `50`: `root = 50`         2.  Insert `30`: `30 < 50`, so `30` becomes `50`'s left child.             ```                 50                /               30             ```         3.  Insert `70`: `70 > 50`, so `70` becomes `50`'s right child.             ```                 50                /  \               30   70             ```         4.  Insert `20`: `20 < 50`, go left to `30`. `20 < 30`, so `20` becomes `30`'s left child.             ```                 50                /  \               30   70              /             20             ```         5.  Insert `40`: `40 < 50`, go left to `30`. `40 > 30`, so `40` becomes `30`'s right child.             ```                 50                /  \               30   70              /  \             20  40             ```         6.  Insert `60`: `60 > 50`, go right to `70`. `60 < 70`, so `60` becomes `70`'s left child.             ```                 50                /  \               30   70              /  \ /             20  40 60             ```         7.  Insert `80`: `80 > 50`, go right to `70`. `80 > 70`, so `80` becomes `70`'s right child.             ```                 50                /  \               30   70              /  \ /  \             20  40 60  80             ```         The node that has `40` as its right child is `30`.

    Practice Next
    More IT DBMS Questions
    ask-question