GATE CS 2015 Set 3 Q13 — Binary Search Trees

To find the element at the lowest (deepest) level, we insert the elements into an initially empty Binary Search Tree (BST) one by one in the given sequence: $71, 65, 84, 69, 67, 83$.

Recall the BST insertion rule: for any node, elements smaller than the node go to its left subtree, and elements larger go to its right subtree.

1. Insert $71$: This becomes the root node.

          71 (Level 0)
       

2. Insert $65$: Since $65 < 71$, it becomes the left child of $71$.

          71 (Level 0)
         /
        65 (Level 1)
       

3. Insert $84$: Since $84 > 71$, it becomes the right child of $71$.

          71 (Level 0)
         /  \
        65   84 (Level 1)
       

4. Insert $69$:
   • $69 < 71 \implies$ go left to $65$
   • $69 > 65 \implies$ right child of $65$

          71 (Level 0)
         /  \
        65   84 (Level 1)
         \
          69 (Level 2)
       

5. Insert $67$:
   • $67 < 71 \implies$ go left to $65$
   • $67 > 65 \implies$ go right to $69$
   • $67 < 69 \implies$ left child of $69$

          71 (Level 0)
         /  \
        65   84 (Level 1)
         \
          69 (Level 2)
         /
        67 (Level 3)
       

6. Insert $83$:
   • $83 > 71 \implies$ go right to $84$
   • $83 < 84 \implies$ left child of $84$

          71 (Level 0)
         /  \
        65   84 (Level 1)
         \   /
         69 83 (Level 2)
         /
        67 (Level 3)
       

Summarizing the levels of each node:

• Level 0: $71$
• Level 1: $65, 84$
• Level 2: $69, 83$
• Level 3: $67$

The element at the lowest level (deepest level) is $67$.