AlgoDaily - Binary Search Trees Interview Questions

Home > Data Structures and Algorithms 🚀 > Binary Search Trees Interview Questions

Binary Search Trees Interview Questions

Binary search trees are a type of binary trees that takes ordering into account.

BSTs are used to store data items which may be inserted, deleted, or retrieved in constant time. In addition, the BST property ensures that the tree is balanced) and that the height of the tree is logarithmic in the number of nodes in it.

They are an example of a self-balancing binary tree: every node in a binary search tree has at most two children, with every child having a value less than its parent. This allows us to perform lookups and insertions by searching through the tree from top to bottom until we find our target node, which has no more than two children itself; at this point we have found our target or there is no such node in our tree.

Because of these attributes, they make for popular interview problems!

Section Menu

How do I use this section?

1. CHALLENGE

Validate a BST

Given a binary search tree like the one below, can you write a function that will return true if it is valid? ` 5 / \ 3 9 / \ 1 4 ` Recall that a BST is val...

Difficulty: 4/10 Mark Completed

2. CHALLENGE

Merge Two Binary Trees

Merging Two Binary Trees The Problem Statement You are presented with two binary trees. Your task is to merge these trees into a single, new binary tree. Merging Binary Trees The Overlap Rule Here's the c...

Difficulty: 5/10 Mark Completed

3. CHALLENGE

Linked List to Binary Search Tree

We're given a sorted singly linked list (that is, a linked list made of nodes with no pointers to the previous node) where the elements are already arranged in ascending order. `js // -9 -> -2 -> 3 -> 5 -> 9 // Linked List Node Definition: function Node(val) { this.val = val; this.next = null; } ` Can you...

Difficulty: 7/10 Mark Completed

4. CHALLENGE

Two Sum from BST

This problem is a fun combination of the famous Two Sum problem combined with a binary search tree. Given the root of a binary search tree, and a target integer K, return true if there exist two nodes in the said tree whose sum equals K. If no pai...

Difficulty: 7/10 Mark Completed

5. CHALLENGE

Lowest Common Ancestor

In the official React documentation, it's recommended that to find out where state data should live, the following steps be taken: Identify every component that renders something based on that state. Find a common owner component (a single component above all the components...

Difficulty: 7/10 Mark Completed

6. CHALLENGE

Counting Univalued Subtrees

Question Can you count all the univalued subtrees in a binary tree, as shown in the figure below? The Problem We are given a binary tree. The challenge is to count all the univalued subtrees in the tree. Just to recall, a subtree is any node along with its...

Difficulty: 6/10 Mark Completed

7. CHALLENGE

Find in Shifted Sorted Matrix

Understanding the Matrix Shift Problem Suppose you have a matrix where each row and column is sorted in ascending order. Your task is to apply two specific types of shifts, described below, and locate a given element x in the transformed matrix. Shift Types Left Circular Shift (l): Definition: Moves the f...

Difficulty: 8/10 Mark Completed

8. CHALLENGE

Sum Nodes Within Range for a Binary Search Tree

A binary search tree is a data structure that has the following properties, Each node in the tree has only two children. The left subtree consists of nodes with values less than the root node. The right subtree consists of nodes with values greater than the root node. Consider that you are given a binary search tree as `ro...

Difficulty: 6/10 Mark Completed

9. CHALLENGE

Create A Binary Search Tree Iterator

We know the binary search tree (BST) structure and the three ways to traverse it: inorder, preorder, and postorder. Now, let's create a class that takes a BST and can traverse it in an inorder fashion. Prompt Implement the BSTInorderTraversal class, whose each object acts as an iterator over the inorder traver...

Difficulty: 8/10 Mark Completed