Binary Search Tree Insertion

Given the root node of a binary search tree and a positive integer, you need to insert a new node with the given value into the BST so that the resulting tree maintains the properties of a binary search tree. If there is more than one configuration possible, return any of the valid trees.

Input:

First line contains an integer 'T' indicating the number of test cases. 
For each test case:
- First line contains the tree elements in level order, with nodes separated by a single space. Use -1 for null nodes.
- Second line contains a positive integer 'val', which is the value to be inserted in the BST.

Output:

Output '1' if a correct tree configuration is returned, otherwise '0', for each test case.

Example:

Input:
1
50 13 72 3 25 66 -1 -1 -1 -1 -1 -1 -1
60
Output:
1

Constraints:

  • 1 <= T <= 5
  • 0 <= N <= 3000
  • 1 <= data <= 10^9 for each node in the BST
  • 1 <= val <= 10^9 for the new node to be inserted
  • All 'data' and 'val' are distinct within a single test case.

Note:

The binary search tree properties: 
a. The left subtree of a node contains only nodes with values less than the node's value.
b. The right subtree of a node contains only nodes with values equal or greater than the node's value.
c. Both left and right subtrees must also be binary search trees.
AnswerBot
1d

Insert a new node with a given value into a binary search tree while maintaining the properties of a BST.

  • Traverse the BST starting from the root node to find the correct position for insertion.

  • Compare...read more

Help your peers!
Add answer anonymously...
Microsoft Corporation Software Developer Intern Interview Questions
Stay ahead in your career. Get AmbitionBox app
qr-code
Helping over 1 Crore job seekers every month in choosing their right fit company
65 L+

Reviews

4 L+

Interviews

4 Cr+

Salaries

1 Cr+

Users/Month

Contribute to help millions

Made with ❤️ in India. Trademarks belong to their respective owners. All rights reserved © 2024 Info Edge (India) Ltd.

Follow us
  • Youtube
  • Instagram
  • LinkedIn
  • Facebook
  • Twitter