Grokking the Art of Recursion for Coding Interviews
Ask Author
Back to course home

0% completed

Vote For New Content
10. Inserting a new node in a BST
Table of Contents

Contents are not accessible

Contents are not accessible

Contents are not accessible

Contents are not accessible

Contents are not accessible

Problem Statement

Write Recursive Approach to Insert New Node in a Binary Search Tree.

Given a binary search tree (BST) and a value to be inserted, write a recursive algorithm to insert a new node with the given value into the BST while maintaining its properties.

Examples

  1. BST Before Insertion:

        4
   / \
  2   7
 / \
1   3

    Input Node: 5 Output BST:

         4
   /    \
  2      7
 / \    /  
1   3  5

    Explanation: The input node with value 5 is inserted as the left child of node 7.

  2. BST Before Insertion:

        6
   / \
  3   8
 / \   \
1   5   9

    Input Node: 4 Output BST:

        6
   / \
  3   8
 / \   \
1   5   9
   /
  4

    Explanation: The input node with value 4 is inserted as the left child of node 5.

  3. BST Before Insertion: Empty BST (null)
    Input Node: 2
    Output BST:

       2

    Explanation: The input node with value 2 becomes the root of the BST.

Constraints:

  • The number of nodes in the tree will be in the range [0, 10<sup>4</sup>].
  • -10<sup>8</sup> <= Node.val <= 10<sup>8</sup>
  • All the values Node.val are unique.
  • -10<sup>8</sup> <= val <= 10<sup>8</sup>
  • It's guaranteed that val does not exist in the original BST.

Try it yourself

Try solving this question here:

Python3
Python3
. . . .

.....

.....

.....

Like the course? Get enrolled and start learning!

Table of Contents

Contents are not accessible

Contents are not accessible

Contents are not accessible

Contents are not accessible

Contents are not accessible