Practice the most popular front-end questions asked in coding interviews with Frontend Churn

00:00:00

Construct a Binary Search Tree and implement that implements`insert()`

, `search()`

, `traverse()`

and `delete()`

methods.

Binary Search Tree is a node-based binary tree data structure which has the following properties:

- The left subtree of a node contains only nodes with keys lesser than the node's key.
- The right subtree of a node contains only nodes with keys greater than the node's key.
- The left and right subtree each must also be a binary search tree.

- Create a Binary Search Tree class.
- Create an
`insert()`

method - that inserts a new node in the Binary Search Tree. - Create an
`delete()`

method - that deletes a new node from the Binary Search Tree. - Create a
`traverse()`

method - that traverses the Binary Search Tree in`preorder`

traversal. - Create a
`search()`

method - that searches for a target value in the Binary Search Tree. If the element is present, return`true`

. Otherwise, return`false`

.

```
const tree = new BST(10);
tree.insert(5);
tree.insert(15);
tree.insert(2);
tree.insert(5);
tree.insert(13);
tree.insert(22);
tree.insert(1);
tree.insert(14);
tree.traverse();
```

```
Output:
10 5 2 1 5 15 13 14 22
```

Click to reveal

Recursion is NOT always required. You can do it iteratively too.

Click to reveal

For `insertion()`

- First search for the place where it has to be inserted.

Click to reveal

For `deletion()`

- List down all the edge cases and handle them all separately.

Click to reveal

For `traversal()`

- Print the value first, then recurse.

Click to reveal

For `search()`

- Keep in mind the properties of a BST - Just like binary search, you can eliminate half of the tree in each iteration.

Uploaded by: Manu Arora

Share this problem on